[POJ2115 C Looooops]拓展欧几里得算法

【算法分析】
实际上是解这样一个方程：
A+C*x=B  (mod 2^k)
C*x=B-A   (mod 2^k)
C*x+(2^k)*y=B-A
注意如果B-A<0的话，要+2^k使之变回>=0。
现在引入小写的a,b,c，并令a=C,b=2^k,c=B-A。
然后求方程ax+bx=c的最小整数解。
于是用拓展欧几里得算法获得ax+bx=gcd(a,b)的解，然后弄到x的最小非负整数解出来即可。
【其他】
第一次深切了解了这个算法。
【CODE】
#include using namespace std;
typedef __int64 lld;
lld A,B,C,k,x,y,P,gcd;

lld exgcd(lld a,lld b){
if (!b){
x=1; y=0;
return a;
}
lld res=exgcd(b,a%b),tx=x,ty=y;
x=ty; y=tx-a/b*ty;
return res;
}

lld solve(lld a,lld b,lld c){
if (!c) return 0;
if (!a) return -1;
lld gcd=exgcd(a,b);
if (c%gcd) return -1;
a/=gcd; b/=gcd; c/=gcd;
x*=c; y*=c;
x=(x%b+b)%b;
return x;
}

int main(){
lld a,b,c;
while (cin >> A >> B >> C >> k){
if (!A && !B && !C && !k) break;
P=1;
for (int i=1;i<=k;i++) P*=2;
a=C; b=P; c=(((B-A)%P)+P)%P;
x=0; y=0;
lld ans=solve(a,b,c);
if (ans==-1) cout << "FOREVER" << endl;
else cout << ans << endl;
}
}