1299. 五指山
2023-09-27 14:27:32 时间
Powered by:NEFU AB-IN
1299. 五指山
-
题意
大圣在佛祖的手掌中。
我们假设佛祖的手掌是一个圆圈,圆圈的长为 n,逆时针记为:0,1,2,…,n−1,而大圣每次飞的距离为 d。
现在大圣所在的位置记为 x,而大圣想去的地方在 y。
要你告诉大圣至少要飞多少次才能到达目的地。
注意:孙悟空的筋斗云只沿着逆时针方向翻。 -
思路
完整推导过程!
其中要注意最后求最小解,做完 e x g c d exgcd exgcd后
- 先判断是否有解,也就是等式右边是否能整除 d d d
- 再将结果放大
- 再推出通解公式,然后除余后面的数即可
-
代码
''' Author: NEFU AB-IN Date: 2022-04-01 16:43:26 FilePath: \ACM\Acwing\1299.py LastEditTime: 2022-04-01 16:43:27 ''' def exgcd(a, b): global x, y if b == 0: x, y = 1, 0 return a d = exgcd(b, a % b) x, y = y, x y -= (a // b) * x return d for _ in range(int(input())): n, D, X, Y = map(int, input().split()) x, y = 0, 0 d = exgcd(D, n) if (Y - X) % d == 0: x *= (Y - X) // d #放大结果 n //= d #处理除余的数 print(x % n) else: print("Impossible")