1 /* 2  POJ2115 C Looooops 3  http://poj.org/problem?id=2115 4  扩展欧几里得 5  题意：求x, s.t. (a+c*x)=b (mod 1<<k) 6         <=> c*x=b-a (mod 1<<k) 7  */ 8 #include <cstdio> 9 #include <algorithm>10 #include <cstring>11 #include <cmath>12 #include <vector>13 #include <queue>14 #include <iostream>15 #include <map>16 #include <set>17 //#define test18 using namespace std;19 const int Nmax=1e6+7;20 long long a,b,c,k,x,y;21 long long ex_gcd(long long a,long long b,long long &x,long long &y)//solve x,y in a*x+b*y=ex_gcd(a,b,x,y)=gcd(a,b);22 {23     if(b==0)24     {25         x=1LL;26         y=0LL;27         return a;28     }29     long long ans=ex_gcd(b,a%b,x,y);30     long long tmp=x;31     x=y;32     y=tmp-a/b*y;33     return ans;34     //x = x0 + (b/gcd)*t35     //y = y0 – (a/gcd)*t36      37 }38 long long get(long long a,long long m,long long c)//get x in a*x=c(mod m)39 {40     //we can solve x,y in a*x+b*y=c <=> c%gcd(a,b)==041     long long x,y;42     long long gcd=ex_gcd(a,m,x,y);43     if(c%gcd!=0)44         return -1;//error45     m/=gcd;46     x*=c/gcd;47     if(m<0)48         m=-m;49     long long ans=x%m;50     while(ans<0)51         ans+=m;52     return ans;53 }54 55 56 int main()57 {58     #ifdef test59     #endif60     //freopen("poj2115.in","r",stdin);61     while(1)62     {63         scanf("%lld%lld%lld%lld",&a,&b,&c,&k);64         if(!a&&!b&&!c&&!k)65             break;66         long long d=b-a;67         //if(d<0)//即使是负数也不用考虑，可以得出正确答案68             //d+=(1LL<<k);69         long long ans=get(c,(1LL<<k),d);70         if(ans==-1)71             printf("FOREVER\n");72         else73             printf("%lld\n",ans);74     }75     return 0;76 }