AGC001 B-Mysterious Light

跟风来写一波AGC…..然后被大佬虐了,zzd他们都是倒着切的…..我好菜啊….

题目传送门

题意:

给你一个长度为n的三角形,然后从离a顶点x的一个点出发开始射光,碰到自己和墙壁会反射,最后回到初始点……
询问经过长度..

分析:

我们发现,光线的路径除了第一次,其余都是在一个平行四边形内部的…..然后有了这个性质我们直接递归算下去就好了……

代码:

#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define LL long long
using namespace std;
template <typename tp>
inline void read(tp &x)
{
    x = 0;char c = getchar();bool f = 0;
    for (; c < '0' || c > '9'; f |= (c == '-'), c = getchar());
    for (; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar());
    if (f) x = -x;
}
LL n, x, ans;
LL Gcd(LL x, LL n)
{
    if (n % x == 0)
        return n * 2 - x;
    ans = n / x * x * 2 + Gcd(n % x, x);
    return ans;
}
signed main()
{
    read(n),read(x);
    printf("%lld\n",Gcd(x, n - x) + n);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注