题目描述
对于C的for(i=A ; i!=B ;i +=C)循环语句，给出A,B,C和k(k表示变量是在k进制下的无符号整数),判断循环次数,不能终止输出"FOREVER".
输入
多组数据，每组一行，A,B,C,k
程序以0 0 0 0结束
输出
一行一个整数，表示循环次数，或者"FOREVER"
样例输入
3 3 2 16
3 7 2 16
7 3 2 16
3 4 2 16
0 0 0 0
样例输出
0
2
32766
FOREVER
这道题翻译一下就是扩展欧几里得解方程，我们知道ax=c(mod p)可以转化为ax+py=c，最后将x，y乘上c/gcd(a,b)就是答案了
这里有一点要注意..答案如果为负要取到最小的正整数解。
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==)
{
x=;
y=;
return a;
}
ll ans=exgcd(b,a%b,x,y);
ll temp=x;
x=y;
y=temp-a/b*y;
return ans;
}
int main()
{
ll a,b,c,d,k,A,B,C,X,Y;
while()
{
cin>>a>>b>>c>>k;
if(a==&&b==&&c==&&k==)
break;
C=b-a;
A=c;
B=(ll)<<k;
if(C<)
{
C+=B;
}
d=exgcd(A,B,X,Y);
if(C%d!=)
{
printf("FOREVER\n");
}
else
{
ll t=B/d;
ll ans=(X*C/d)%B;
ans=(ans%t+t)%t;
cout<<ans<<endl;
}
}
}