嗯...
题目链接:http://poj.org/problem?ID=2115
(A+s*C)%2^k=B (A+s*C)≡B(mod 2^k) s*C-m*2^k=B-A ax+by=c 有一个问题,b没必要是负的,反正正负a和b的线性组合集都一样,况且此题不需要y AC代码:
1 #include<cstdio> 2 #include<iostream> 3 4 using namespace std; 5 6 inline voID exgcd(long long a,long long b,long long &g,long long &x,long long &y){ 7 if(!b) { g = a; x = 1; y = 0;} 8 else { exgcd(b,a % b,g,y,x); y -= x * (a / b);} 9 }10 11 int main(){12 long long a,b,c,A,B,C,k,x,y;13 while(~scanf("%lld%lld%lld%lld",&A,&B,&C,&k)){14 if(!A && !B && !C && !k) break;15 a = C; b = 1ll << k; c = B - A;16 exgcd(a,y);17 if(c % g) printf("FOREVER\n");18 else{19 c /= g; b /= g;20 printf("%lld\n",(x % b * c % b + b) % b);21 }22 }23 return 0;24 }AC代码 总结
以上是内存溢出为你收集整理的POJ 2115 C Looooops(exgcd)全部内容,希望文章能够帮你解决POJ 2115 C Looooops(exgcd)所遇到的程序开发问题。
如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)