extend_gcd.zip_欧几里德联合

#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> using namespace std; #define ll long long ll ext_gcd(ll a,ll b,ll &x,ll &y) { if(b==0) { x=1; y=0; return a; } ll d=ext_gcd(b,a%b,y,x); y-=a/b*x; return d; } ll ax_b_mod_n(ll a, ll b, ll n) { ll x,y,d,t; d=ext_gcd(a,b,x,y); if(n%d==0) { x=n/d*x; t=b/d; if(t<0) t=-t; x=(x%t+t)%t; return x; } return -1; } int main() { ll x,y,a,b,n,a1,b1,n1,c,k; ll d[50]; d[0]=1; for(int i=1;i<=49;i++) d[i]=d[i-1]*2; while(scanf("%I64d%I64d%I64d%I64d",&a,&b,&c,&k)==4) { if(!(a || b || c || k)) break; if(c==0) { if(a==b) printf("0\n"); else printf("FOREVER\n"); continue; } a1=c; b1=d[k]; n1=b-a; ll ans=ax_b_mod_n(a1,b1,n1); if(ans==-1) printf("FOREVER\n"); else printf("%I64d\n",ans); } return 0; }