poj-2115-C Looooops-扩展欧几里德
很模版的一道求扩展欧几里德的题目。
可以根据a，b，c，k得知：
题意是求是不是存在d，使得c*d=b-a+n*2^k
求扩展欧几里德：
求的结果为d=ax+by。其中x，y为最小结果。
#include<iostream>using namespace std;__int64 exgcd(__int64 a,__int64 b,__int64& x,__int64& y){if(b==0){x=1;y=0;return a;}__int64 d;__int64 xx;d=exgcd(b,a%b,x,y);xx=x;x=y;y=xx-a/b*y;return d;}int main(){__int64 A,B,C,k;while(scanf("%I64d %I64d %I64d %I64d",&A,&B,&C,&k)){if(!A && !B && !C && !k)break;__int64 a=C;__int64 b=B-A;__int64 n=(__int64)1<<k; //2^k__int64 x,y;__int64 d;d=exgcd(a,n,x,y);if(b%d!=0)cout<<"FOREVER"<<endl;else{x=(x*(b/d))%n;x=(x%(n/d)+n/d)%(n/d);printf("%I64d\n",x);}}return 0;}