【AtCoder】AGC001 Mysterious Light
题目
题目大意
在一个边长为的等边三角形中,你按如图所示(距点单位长的位置)的方法发射一道激光,激光遇到三角形的边或者之前的激光都会反弹,激光回到原点就结束,问一共走了多远。
思路
在平行四边形中,激光由开始反射,能够“完整”地反射到,然后进入平行四边形。
在平行四边形中,激光由开始反射,能够“完整”地反射到,发现反射完成。
于是递归求解。
设表示在边长为的平行四边形中激光一共走过的距离,则答案为(加上最开始两个轨迹的长度)
如上图,在平行四边形中,,所以激光完整走过的距离是。
然后激光进入平行四边形,在平行四边形中,。
于是:
边界很简单,当是的倍数时,说明激光能够回到原点,返回,注意要减掉一个(观察样例)。
注意开long long
。
代码
#include<cstdio>
long long Solve(long long a,long long b){
if(b%a==0)
return b/a*a*2-a;
return b/a*a*2+Solve(b%a,a);
}
int main(){
long long N,X;
scanf("%lld%lld",&N,&X);
printf("%lld",N+Solve(X,N-X));
}