C Looooops POJ - 2115

​​http://poj.org/problem?id=2115​​

拓展歐幾裡德裸題 以cc為a (1<<k)為b (bb-aa)為c 求(a*x)%b=c得最小非負整數解即可

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=50;

ll pre[maxn];

void init()
{
    int i;
    pre[0]=1ll;
    for(i=1;i<=32;i++){
        pre[i]=2ll*pre[i-1];
    }
}

void exgcd(ll a,ll b,ll& x,ll& y)
{
    ll tx,ty;
    if(b==0){
        x=1,y=0;
        return;
    }
    exgcd(b,a%b,tx,ty);
    x=ty,y=tx-a/b*ty;
}

ll getabs(ll val)
{
    if(val>=0) return val;
    else return -val;
}

int main()
{
    ll aa,bb,cc,gcd;
    ll a,b,c,x,y,s;
    int k;
    init();
    while(scanf("%lld%lld%lld%d",&aa,&bb,&cc,&k)!=EOF){
        if(aa==0&&bb==0&&cc==0&&k==0) break;
        if(aa==bb) printf("0\n");
        else if(cc==0) printf("FOREVER\n");
        else{
            a=cc,b=pre[k],c=bb-aa;
            exgcd(a,b,x,y);
            gcd=a*x+b*y;
            if(c%gcd!=0) printf("FOREVER\n");
            else{
                s=getabs(b/gcd);
                x*=(c/gcd);
                x=(x%s+s)%s;
                printf("%lld\n",x);
            }
        }
    }
    return 0;
}