poj 2115 C Looooops 扩展欧几里得算法

题意：
对于C的for(i=A ; i!=B ;i +=C)循环语句，问循环几次才会结束，其中所有的数(mod2^k)。
若在有限次内结束，则输出循环次数。否则输出死循环。
分析：
模线性方程的题目：题目可转化为Cx=（B-A）mod（2^k）求x的最小解？
然后就是用扩展欧几里得算法求解了。
详细的解题报告参考：http://blog.csdn.net/non_cease/article/details/7364092

#include<iostream>
#include<cstdio>
#include<set>
using namespace std;
typedef long long ll;
const int N=1e5+9;

void gcd(ll a,ll b,ll& d,ll& x,ll& y)
{
    if(!b){d=a;x=1;y=0;}
    else{
        gcd(b,a%b,d,y,x);
        y-=x*(a/b);
    }
}
int main()
{
    //freopen("f.txt","r",stdin);
    ll a,b,c,k;
    while(~scanf("%lld%lld%lld%lld",&a,&b,&c,&k)&&(a+b+c+k)){
        ll d,x,y;
        gcd(c,1LL<<k,d,x,y);
        if((b-a)%d!=0)puts("FOREVER");
        else{
            x=x*(b-a)/d;
            ll t=(1LL<<k)/d;
            x=(x%t+t)%t;
            printf("%lld
",x);
        }
    }
    return 0;
}