poj 2115 C Looooops

/*
* @Author: Lyucheng
* @Date:   2017-08-07 08:57:28
* @Last Modified by:   Lyucheng
* @Last Modified time: 2017-08-09 16:10:54
*/
/*
 题意：给你一个简单的循环for(int i=A;i!=B;i+=C)，i是16位得数，问你循环结束的次数，如果是死循环的话，就输出死循环

 思路：刚开始想简单的模拟一下，但是超时至少模拟2^k次循环，扩展欧几里得问题完美解决这个问题
    题意循环可以转化成公式 
        ( A + x*C ) mod (1<<K) = B 
    因为 题意中的A 肯定是小于(1<<k)的所以化简为
        x*C mod (1<<k) = B - A 
    这个就是扩展欧几里得定理求膜线性方程
    令D = B - A , n= (1<<k) 得
        x*C mod n = D
    则
        x*C - y*n =D 
    这就是
        a*x+b*y=c的扩展欧几里得定理解不定方程了
*/
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>

#define LL long long

using namespace std;

LL A,B,C,K;
LL x,y;
LL GCD;
LL tol;

void exgcd(LL a,LL b,LL &x,LL &y,LL &d)
{
    if(!b){ 
        d=a; x=1; y=0;
    }
    else {
        exgcd(b,a%b,y,x,d);
        y-=x*(a/b);
    }
}

int main(){ 
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    while(scanf("%I64d%I64d%I64d%I64d",&A,&B,&C,&K)!=EOF&&(A||B||C||K)){
        if(A==B){
            puts("0");
            continue;
        }
        B-=A;
        tol=(1LL<<K);
        exgcd(tol,C,x,y,GCD);
        if(B%GCD!=0){//无解
            puts("FOREVER");
            continue;
        }else{
            x*=(B/GCD);
            y*=(B/GCD);
            y=(y%(tol/GCD)+tol/GCD)%(tol/GCD);  
            printf("%I64d\n", y);  
        }
    }    
    return 0;
}