输入 A，B，C,k，判断 for (variable = A; variable != B; variable += C) 循环执行几次
题目转化为 (ans*C+A)=B(mod 2^k)，求解一元线性同余方程裸题
ll ex_gcd(ll a,ll b,ll &x,ll &y) //ax+by=gcd(a,b) { ll gcd=a; if(!b) x=1,y=0; else { gcd=ex_gcd(b,a%b,y,x); y-=(a/b)*x; } return gcd; } void rep(ll &x,ll mod) { x%=mod; x+=mod; x%=mod; //if(!x) x=mod; } void linear(ll a,ll b,ll c){ //求解 ax=b(mod c) ll x,y; ll g=ex_gcd(a,c,x,y); //ax+cy=b if(b%g){ puts("FOREVER"); return ; } x=x*b/g; rep(x,c/g); pll(x); } int main() { //IOS; ll A,B,C; while(scanf("%lld %lld %lld %lld",&A,&B,&C,&k)==4){ if(A==0 && B==0 && C==0 && k==0) break; linear(C,B-A,1ll<<k); } //PAUSE; return 0; }
