無符號k位數溢出就相當于mod 2k，然后設循環x次A等于B，就可以列出方程：
$$ Cx+A \equiv B \pmod {2^k} $$ $$ Cx \equiv B-A \pmod {2^k} $$
最后就用擴展歐幾里得算法求出這個線性同余方程的最小非負整數解。
1 #include<cstdio> 2 #include<cstring> 3 #define mod(x,y) (((x)%(y)+(y))%(y)) 4 #define ll long long 5 ll exgcd(ll a,ll b,ll &x,ll &y){ 6 if(b==0){ 7 x=1; y=0; 8 return a; 9 } 10 ll d=exgcd(b,a%b,x,y); 11 ll t=y; 12 y=x-a/b*y; 13 x=t; 14 return d; 15 } 16 ll MLES(ll a,ll b,ll n){ 17 ll x,y; 18 ll d=exgcd(a,n,x,y); 19 if(b%d) return -1; 20 return mod(x*(b/d),n/d); 21 } 22 int main(){ 23 ll a,b,c,k; 24 while(~scanf("%lld%lld%lld%lld",&a,&b,&c,&k) && (a||b||c||k)){ 25 k=1LL<<k; 26 ll res=MLES(c,b-a,k); 27 if(res==-1) puts("FOREVER"); 28 else printf("%lld\n",res); 29 } 30 return 0; 31 }
?
)
