题目描述
对于 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
从题目中抽象出线性同余方程,再通过扩展欧几里得算法解方程,并得到最小正整数解(对b/d取模(要保证正整数))
C++ 代码
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;//k<=32,int=2^31-1,所以这里的数据会爆int
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(){
ll a,b,c,k;
while(cin>>a>>b>>c>>k,a||b||c||k){
ll x,y;
ll z=1ll<<k;//(1ll即1 (long long ))
ll d=exgcd(c,z,x,y);
if((b-a)%d)cout<<"FOREVER"<<endl;
else{
x*=(b-a)/d;
z/=d;
cout<<(x%z+z)%z<<endl;//最少的循环次数
}
}
return 0;
}