对于 C 语言的循环语句，形如：
for (variable = A; variable != B; variable += C)
statement;
请问在 k 位存储系统中循环几次才会结束。
若在有限次内结束，则输出循环次数。否则输出死循环。
输入格式
多组数据，每组数据一行四个整数 A,B,C,k。
读入以 0 0 0 0 结束。
输出格式
若在有限次内结束，则输出循环次数。
否则输出 FOREVER。
数据范围
1≤k≤32,
0≤A,B,C<2k
输入样例：
3 3 2 16
3 7 2 16
7 3 2 16
3 4 2 16
0 0 0 0
输出样例：
0
2
32766
FOREVER
这道题很明显就是一个欧几里得算法的一个变形。
这是算法的一个变形
a
+
n
∗
c
−
(
1
<
<
k
)
∗
m
=
b
a + n * c- (1 << k ) * m = b
a+n∗c−(1<<k)∗m=b
n
∗
c
−
(
1
<
<
k
)
∗
m
=
b
−
a
n * c- (1 << k ) * m = b - a
n∗c−(1<<k)∗m=b−a
a
x
+
b
y
=
g
c
d
(
a
,
b
)
ax+by=gcd(a,b)
ax+by=gcd(a,b)
然后使用扩展欧几里得算法，去把 c,(1<<k)作为扩展欧几里得的a和b,然后去求n，m
做这道题的固定套路是对m除以k，然后用类似于求哈希函数一样，最后输出答案
代码如下。
#include<iostream>
using namespace std;
typedef long long LL;
LL exgcd(LL a,LL b,LL &x,LL &y)
{
if(!b)
{
x=1;y=0;
return a;
}
LL d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int main(void)
{
LL a,b,c,k;
while(cin>>a>>b>>c>>k,a||b||c||k)
{
k=(LL)1<<k;
LL n,m;
LL d=exgcd(c,k,n,m);
if((b-a)%d==0)
{
n*=(b-a)/d;
LL z=k/d;
cout<<(n%z+z)%z<<endl;
}
else
puts("FOREVER");
}
}