扩展欧几里得算法算法例题——1299. 五指山、1301. C 循环

1299. 五指山

大圣在佛祖的手掌中。

我们假设佛祖的手掌是一个圆圈，圆圈的长为 n，逆时针记为：0,1,2,…,n?1，而大圣每次飞的距离为 d。

现在大圣所在的位置记为 x，而大圣想去的地方在 y。

要你告诉大圣至少要飞多少次才能到达目的地。

注意：孙悟空的筋斗云只沿着逆时针方向翻。

输入格式
有多组测试数据。

第一行是一个正整数 T，表示测试数据的组数；

每组测试数据包括一行，四个非负整数，分别为如来手掌圆圈的长度 n，筋斗所能飞的距离 d，大圣的初始位置 x 和大圣想去的地方 y。

输出格式
对于每组测试数据，输出一行，给出大圣最少要翻多少个筋斗云才能到达目的地。

如果无论翻多少个筋斗云也不能到达，输出 Impossible。

数据范围
2<n<109,
0<d<n,
0≤x,y<n
输入样例：
2
3 2 0 2
3 2 0 1
输出样例：
1
2
难度：简单
时/空限制：1s / 64MB
总通过数：259
总尝试数：544
来源：《信息学奥赛一本通》
算法标签

裴蜀定理：
指对于任意正整数对(a,b)，如果gcd(a,b) = d，则一定存在非零整数x和y ，使得 ax+by = d
扩展欧几里得算法 可以求出一组系数x0,y0,d。

我们来分情况讨论一下扩展欧几里得定理：

1. 当b = 0时，a和b的最大公约数为a.则x = 1;
2. 当b ≠ 0时，
   by+(a mod b)x = gcd(a,b)
   ->by+(a - a/b * b)x = gcd(a,b)
   ->ax+b(y - a/b * x) = gcd(a,b)
   即当我们用扩展欧几里得定理求x和y时，欧几里得定理每递归一次x不用变,y->y-a/b * x即可
   如果我们求出x和y的一对，我们记为x0和y0
   那么其他的x和y可以通过x0，y0表示:
   令a=a/gcd(a,b) , b=b/gcd(a,b)，任意意一组解：
   $$x=x0+k?b$$
   $$y=y0?k?a$$
   证明：
   ax0+by0 = gcd(a,b)
   ax+b*y = gcd(a,b)
   如果x0比x小，那么y0就应该比y大，这样加起来的结果才可能相同
   所以，a(x-x0) = b(y0-y);
   两边同时除以一个gcd(a,b)
   得到：a(x-x0) = b(y0-y)
   那么b就应该能整除a(x-x0)，又因为a和b互质，
   所以b应该能整除(x-x0)
   所以(x-x0) = kb则 x = x0+kb
   y = y0-ka
   这里的k可正可负

题意是让我们求x+bd = y+an （变量来源看题意）,整理得：-an+bd = y-x
但是我们得扩展欧几里得定理只能求 -an+bd = gcd(n,d)中的a和b，但是很容易看出y-x应该为gcd(n,d)的整数倍，否则无解。
因此我们只需要判断y-x是否为gcd(n,d)的整数倍就能判断是否有解了。
若有解我们利用扩展欧几里得定理就可以求得-an+bd = gcd(n,d)中的a和b，然后将a和b扩大 (y-x)/gcd(n,d)倍
就可以得到一组a0和b0，因为之前我们证过了获得一组解后其他解就可以表示出来了，我们只需要求一下所有解中的最小值就可以了（注意我们的b只能是正数，你总不能让大圣反着翻吧）
即：
求一下b = b0+k*(n/gcd(n,d))的最小值即可
minb = b0%(n/gcd(n,d));

IA = lambda : map(int, input().split())
T = int(input())
# 返回ax + by = gcd(a,b)方程的一组解x0，y0以及gcd(a,b)
def exgcd(a, b):if b == 0:return 1, 0, ax, y, d = exgcd(b, a % b)return y, x - a // b * y, d
for _ in range(T):n, d, x, y = IA()x0, y0, gcd = exgcd(n, d)if (y - x) % gcd !=0 :print("Impossible")else:n //= gcdy0 *= (y - x) // gcdprint((y0 % n + n) % n)

1301. C 循环

对于 C 语言的循环语句，形如：

for (variable = A; variable != B; variable += C)statement;

请问在 k 位存储系统中循环几次才会结束。

若在有限次内结束，则输出循环次数。否则输出死循环。

输入格式
多组数据，每组数据一行四个整数 A,B,C,k。

读入以 0 0 0 0 结束。

输出格式
若在有限次内结束，则输出循环次数。

否则输出 FOREVER。

数据范围
1≤k≤32,
0≤A,B,C<2k
输入样例：
3 3 2 16
3 7 2 16
7 3 2 16
3 4 2 16
0 0 0 0
输出样例：
0
2
32766
FOREVER

题解
k位系统的意思：存数只能存最后k位，即%2^k的结果。
即求
$$(A+xC)mod{2}^k=B$$
$$A+xC?y?2^k=B$$
$$xC?y?2^k=B?A$$

IA = lambda : map(int, input().split())def exgcd(a, b):if b == 0:return 1, 0, ax, y, d = exgcd(b, a%b)return y, x - a // b * y, d
while True:try:A, B, C, k = IA()if A == 0 and B == 0 and C == 0 and k ==0:breakx, y, gcd = exgcd(C, 1 << k)if (B - A) % gcd != 0:print("FOREVER")else:t = (1 << k) // gcdx *= (B - A) // gcdprint((x % t + t) % t)except:break