POJ 2115 C Looops(一元線形同余方程式)

Description問ループ文for(variable=A;variable!=B;variable+=C);実行された回数x(結果mod 2^k)Inputの複数組の入力は、各組の使用例の1行に4つの整数A,B,C,kを含み、0 0 0 0 0で入力Outputの各組の使用例について出力サイクル数xを終了する.デッドサイクルであれば出力FOREVER Sample Input 3 3 3 2 16 3 7 2 16 7 3 2 16 3 4 2 16 0 0 0 Sample Output 0 2 32766 FOREVER Solution問題はA+C*x=b(mod 2^k)を求める最小整数解に変換され、すなわち一元線形同余方程式C*x=B-A(mod 2^k)、テンプレート問題Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector> 
using namespace std;
typedef long long ll;
ll extend_gcd(ll a,ll b,ll & x,ll & y)//      ,  ax+by=gcd(a,b) 
{ 
    ll d=a;
    if(b!=0)
    {
        d=extend_gcd(b,a%b,y,x);
        y-=(a/b)*x;
    }
    else 
    {
        x=1;
        y=0;
    }
    return d;
}
void linear(ll a,ll b,ll c)//          ax=b(mod c)
{
    ll x,y;
    ll g=extend_gcd(a,c,x,y);
    if(b%g)
    {
        printf("FOREVER
");
        return ;
    }
    x=x*(b/g);
    ll mod=c/g;
    x=(x%mod+mod)%mod;
    printf("%lld
",x);
    return ;
}
int main()
{
    ll a,b,c,k;
    while(scanf("%lld%lld%lld%lld",&a,&b,&c,&k),a||b||c||k)
    {
        ll A=c,C=1ll<<k,B=b-a;//  1ll 
        linear(A,B,C); 
    }
    return 0;
}