C Looooops （扩展欧几里得） HQG

欧几里得） HQG"/>

C Looooops （扩展欧几里得） HQG

又是个裸的。

直接 exgcd(c,1<<k,x,y), e x g c d ( c , 1 << k , x , y ) , $exgcd(c,1<<k,x,y),$判断负数即可。

水。。。

#include <bits/stdc++.h>
using namespace std ;
typedef long long ll ;
ll a,b,c,d,k,A,B,C,D,e,x,y ;ll exgcd(ll a,ll b,ll &D,ll &x,ll &y){if (b==0){x=1;y=0 ;D=a;}else {exgcd(b,a%b,D,y,x) ;y-=(a/b)*x ;} 
}
int main(){while(scanf("%lld%lld%lld%lld",&a,&b,&c,&k) && (a|b|c|k)){C=b-a ;if (C==0){printf("0\n") ;continue ;}A=c ;B=(ll)1<<k ;exgcd(A,B,D,x,y) ;if (C%D){printf("FOREVER\n") ;continue ;}e=B/D;x=(((x*C/D)%e)+e)%e;printf("%lld\n",x);} 
}