算法 扩展欧几里得
本题本质上与五指山 一样
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
LL exgcd(LL a,LL b, LL &x,LL &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
LL d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int main()
{
LL A,B,C,K;
//原问题为(A+x*C) mod 2^k =B
//转换为A+x*C-y*2^k=B
//移项得x*C-y*2^k=B-A;
while(cin>>A>>B>>C>>K,A||B||C||K)
{
LL x,y;
LL Z=1ll<<K;//z=2^k,得写1ll
LL gcd=exgcd(C,Z,x,y);
if((B-A)%gcd)
{
puts("FOREVER");
}
else
{
x=x*(B-A)/gcd;
Z=Z/gcd;
cout<<(x%Z+Z)%Z<<endl;
}
}
return 0;
}