信息学奥赛一本通 1640：C Looooops

【题目链接】

ybt 1640：C Looooops
LOJ 10218. 「一本通 6.4 练习 4」C Looooops

【题目考点】

1. 线性同余方程

相关知识见 【模板】洛谷 P1082 [NOIP 2012 提高组] 同余方程

【解题思路】

在C或C++的k kk位存储系统，可以存储[ 0 , 2 k − 1 ] [0, 2^k-1][0,2k−1]范围内的整数。如unsigned int类型的范围为[ 0 , 2 32 − 1 ] [0, 2^{32}-1][0,232−1]，unsigned long long类型的范围为[ 0 , 2 64 − 1 ] [0, 2^{64}-1][0,264−1]。
当变量的数值超出了该数据类型可以表示的范围，会发生“自然溢出”，变量在二进制下只会保留末k kk位，在数值角度看相当于进行了m o d 2 k \bmod 2^kmod2k操作。
for (variable = A; variable != B; variable += C)
该代码的意义为：变量初值为A，每次循环变量的值增加C，当变量的值等于B时跳出循环。
假设进行了x xx次循环，则有A + x C m o d 2 k = B A+xC \bmod 2^k = BA+xCmod2k=B。
或列成同余方程A + x C ≡ B ( m o d 2 k ) A+xC\equiv B \pmod{2^k}A+xC≡B(mod2k)
整理得C x ≡ B − A ( m o d 2 k ) Cx\equiv B-A \pmod{2^k}Cx≡B−A(mod2k)

• 如果g c d ( C , 2 k ) ∣ ( B − A ) gcd(C, 2^k)\mid (B-A)gcd(C,2k)∣(B−A)，则该方程有解，通过扩展欧几里得算法求线性同余方程的解。
  -如果g c d ( C , 2 k ) ∤ ( B − A ) gcd(C, 2^k)\nmid (B-A)gcd(C,2k)∤(B−A)，则该方程无解，即无论进行几次循环，变量的值都无法等于B BB，输出FOREVER。

【题解代码】

解法1：扩展欧几里得算法直接求解线性同余方程

#include<bits/stdc++.h>usingnamespacestd;#defineN25#defineMOD(a,b)(((a)%(b)+(b))%(b))typedeflonglongLL;voidexgcd(LL a,LL b,LL&x,LL&y,LL&g){if(b==0){x=1,y=0,g=a;return;}exgcd(b,a%b,y,x,g);y-=a/b*x;}intmain(){LL a,b,c,k,x,y,g;while(cin>>a>>b>>c>>k&&!(a==0&&b==0&&c==0&&k==0)){exgcd(c,1LL<<k,x,y,g);if((b-a)%g==0)cout<<MOD(x*(b-a)/g,(1LL<<k)/g)<<endl;elsecout<<"FOREVER"<<endl;}return0;}

解法2：先求乘法逆元再解线性同余方程

#include<bits/stdc++.h>usingnamespacestd;#defineN25#defineMOD(a,b)(((a)%(b)+(b))%(b))typedeflonglongLL;voidexgcd(LL a,LL b,LL&x,LL&y){if(b==0){x=1,y=0;return;}exgcd(b,a%b,y,x);y-=a/b*x;}LLgcd(LL a,LL b){if(b==0)returna;returngcd(b,a%b);}LLinv(LL a,LL m){LL x,y;exgcd(a,m,x,y);returnMOD(x,m);}intmain(){LL a,b,c,k,x,y,g;while(cin>>a>>b>>c>>k&&!(a==0&&b==0&&c==0&&k==0)){g=gcd(c,1LL<<k);if((b-a)%g==0)cout<<MOD((b-a)/g*inv(c,1LL<<k),(1LL<<k)/g)<<endl;elsecout<<"FOREVER"<<endl;}return0;}