这两题都是求解同余方程，并要求出最小正整数解的
对于给定的Ax=B(mod C) 要求x的最小正整数解
首先这个式子可转化为 Ax+Cy=B，那么先用exgcd求出Ax+Cy=gcd(A,C)的解x
然后这个式子的一个特解就是 （B/gcd(A,C)）* x
要注意如果gcd(A,C)无法整除B，那么这个式子无解
然后是求出最小整数解
Ax+Cy=B 方程的通解是 x+k*C/gcd(A,C),
另s=C/gcd(A,C)
所以最小整数解是(x%s+s)%s
青蛙题
/*
x+km=y+kn(mod L) x+km+t*L=y+kn
k(m-n)+(x-y)=-t*L
k(n-m)-(x-y)=t*L 要求出k
即(n-m)k = x-y(mod L)
那么(x-y)%gcd(n-m,L)==0 如果(x-y)%gcd(n-m,L)!=0，那么就是无解 用exgcd(n-m,l,x,y)出k0即可
答案是(x-y)/gcd(n-m,L)*k0+l/gcd(n-m,l)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long
ll x,y,m,n,L;
ll exgcd(ll a,ll b,ll &x,ll &y){
if(b==){x=;y=;return a;}
ll d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int main(){
while(cin>>x>>y>>m>>n>>L){
ll a=n-m,b=L,c=x-y,k,u;
ll d=exgcd(a,b,k,u);
if(c%d!=){
puts("Impossible");
continue;
}
k=k*(c/d);//该方程特解
ll m=b/d;
printf("%lld\n",(k%m+m)%m);
}
}
looop题
/*
Cx=B-A(mod L)
转化为求同余方程
Cx+Ly=B-A
d=gcd(C,L)
d|B-A,则有解
exgcd(C,L,x,y)解得x
先求出一个特解x=(B-A)/d*x
然后再求最小整数解即可
*/
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define ll long long
ll exgcd(ll a,ll b,ll &x,ll &y){
if(!b){x=,y=;return a;}
ll d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int main(){
ll A,B,C,k,L;
while(cin>>A>>B>>C>>k && (A||B||C||k) ){
L=;
for(int i=;i<=k;i++)
L*=;
ll d,x,y;
d=exgcd(C,L,x,y);
if((B-A)%d!=){
puts("FOREVER");
continue;
} x=(B-A)/d*x;
ll s=L/d;
cout<<(x%s+s)%s<<endl;
}
}