首页 > 代码库 > POJ2115:C Looooops（一元线性同余方程）
POJ2115:C Looooops（一元线性同余方程）
题目： http://poj.org/problem?id=2115
前两天用二元一次线性方程解过，万变不离其宗都是利用扩展欧几里得来接最优解。
分析：
数论了解的还不算太多，解的时候，碰到了不小的麻烦。
设答案为x，n = (1<<k), 则 (A+C*x) % n == B
即 (A+C*x) ≡ B (mod n)//-----结果显而易见两边的（a+cx)%n==b<n
化简得 C*x ≡ (B-A） （mod n)//----同余模的性质a-c==b-c(mod n)在a==b(mod n)的前提下
自己晕了，还是掌握的不好，和之前的代码一样，只是推导的方法多了一种。
#include <iostream>#include <stdio.h>#include <string.h>#include <algorithm>#include <math.h>using namespace std;long long a,b,c,k;long long x1,x2;long long gcd(long long a,long long b){ return b==0?a:gcd(b,a%b);}void extend(long long A,long long B,long long &x1,long long &y1){ if(B==0) { x1=1; y1=0; return ; } extend(B,A%B,x1,y1); long long t=x1; x1=y1; y1=t-(A/B)*y1;}int main(){ while(scanf("%lld%lld%lld%lld",&a,&b,&c,&k)!=EOF) { if(a==0&&b==0&&c==0&&k==0) break; long long A=c; long long B=pow(2,k); long long C=b-a; long long temp=gcd(A,B); if(C%temp) { printf("FOREVER\n"); continue; } A/=temp; B/=temp; C/=temp; extend(A,B,x1,x2); long long t=(C*x1%B+B)%B; printf("%lld\n",t); } return 0;}
POJ2115:C Looooops（一元线性同余方程）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。