POJ 2115：http://poj.org/problem?id=2115
思路
设循环T次 则要满足A≡(B+CT)(mod 2k)
可得 A=B+CT+m*2k
移项得C*T+2k*m=B-A （因为要满足B大于A）即是Exgcd的标准式子了
代码
#include<iostream>
#include<cstdio>
using namespace std;
#define ll long long
ll A,B,C,T,k;
int gcd(ll a,ll b)
{
if(!b) return a;
else return gcd(b,a%b);
}
void exgcd(ll a,ll b,ll &x,ll &y)
{
if(!b)
{
x=;
y=;
}
else
{
exgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
}
}
int main()
{
while()
{
scanf("%lld%lld%lld%lld",&A,&B,&C,&k);
if(!A&&!B&&!C&&!k) break;
ll a=C,b=,c=B-A,x,y;
for(ll i=;i<k;i++)
b*=;//计算2^k
ll d=gcd(a,b);
if(c%d==)//如果有解进行Exgcd
{
a/=d,b/=d,c/=d;
exgcd(a,b,x,y);
x=((c*x)%b+b)%b;
}
else
{
printf("FOREVER\n");
continue;//如果无解则是无限循环
}
printf("%lld\n",x);
}
}