【题解】POJ 2115 C Looooops （Exgcd）

POJ 2115：http://poj.org/problem?id=2115

思路

设循环T次 则要满足A≡(B+CT)(mod 2^k)

可得 A=B+CT+m*2^k

移项得C*T+2^k*m=B-A （因为要满足B大于A）即是Exgcd的标准式子了

代码

#include<iostream> #include<cstdio> using namespace std; #define ll long long ll A,B,C,T,k; int gcd(ll a,ll b) { if(!b) return a; else return gcd(b,a%b); } void exgcd(ll a,ll b,ll &x,ll &y) { if(!b) { x=1; y=0; } else { exgcd(b,a%b,x,y); int t=x; x=y; y=t-a/b*y; } } int main() { while(1) { scanf("%lld%lld%lld%lld",&A,&B,&C,&k); if(!A&&!B&&!C&&!k) break; ll a=C,b=2,c=B-A,x,y; for(ll i=1;i<k;i++) b*=2;//计算2^k ll d=gcd(a,b); if(c%d==0)//如果有解进行Exgcd { a/=d,b/=d,c/=d; exgcd(a,b,x,y); x=((c*x)%b+b)%b; } else { printf("FOREVER\n"); continue;//如果无解则是无限循环 } printf("%lld\n",x); } } View Code

 

转载于:https://www.cnblogs.com/BrokenString/p/9676158.html

相关资源：JAVA上百实例源码以及开源项目