当前位置:网站首页>[atcoder1980] mystious light (mathematical simulation)

[atcoder1980] mystious light (mathematical simulation)

2022-06-11 07:36:00 CaptainHarryChen

The question

There is a side length of N(2<=N<=10^12) An equilateral triangle of mirrors , Set node as a,b,c, from ab Take a little bit of p, bring ap=X(1<=X<=N-1), from p A mysterious light is emitted horizontally to the right , After several reflections , go back to p spot . This mysterious light has one characteristic , He will leave a mirror on the path he has walked ( The light will be reflected by the path it has traveled ), Please come back finally p a.m. , The distance the light travels .

Answer key

It is found that light always travels in a parallelogram , Parallelogram keeps shrinking , Pictured

Let the short side of a parallelogram be a a , The long side is b
The short side of the next parallelogram is b mod a b   m o d   a , The long side is a a , The journey of this transfer is 2 a × ( b / a )
Until you come to the parallelogram whose side length is 0, Attention at the end , The last walk on the left is not 2a 2 a , yes a a <script type="math/tex" id="MathJax-Element-389">a</script>, It needs to be reduced once .

Code

#include<cstdio>
#include<algorithm>
using namespace std;

long long solve(long long a,long long b)
{
    if(a==0)
        return 0;
    long long res=a*(b/a)*2;
    if(b%a==0)
    {
        res-=a;
        return res;
    }
    return res+solve(b%a,a);
}

int main()
{
    long long N,X;
    scanf("%lld%lld",&N,&X);
    long long ans=N+solve(min(X,N-X),max(X,N-X));
    printf("%lld\n",ans);

    return 0;
}
原网站

版权声明
本文为[CaptainHarryChen]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/162/202206110723240885.html