题目大意
求同余方程Cx≡B-A(2^k)的最小正整数解
题解
可以转化为Cx-(2^k)y=B-A,然后用扩展欧几里得解出即可。。。
代码：
#include <iostream>
using namespace std;
typedef long long LL;
void extended_gcd(LL a,LL b,LL &d,LL &x,LL &y)
{
if(!b)
{
d=a,x=1,y=0;
}
else
{
extended_gcd(b,a%b,d,y,x);
y-=x*(a/b);
}
}
int main()
{
LL a,b,k,c,x,y,d,p;
while(cin>>a>>b>>c>>k&&a+b+c+k)
{
p=1LL<<k;
extended_gcd(c,p,d,x,y);
if((b-a)%d)
{
cout<<"FOREVER"<<endl;
continue;
}
x=x*(b-a)/d;
x=(x%(p/d)+p/d)%(p/d);
cout<<x<<endl;
}
return 0;
}