首页 > 代码库 > POJ 2891 中国剩余定理的非互质形式
POJ 2891 中国剩余定理的非互质形式
中国剩余定理的非互质形式
任意n个表达式一对对处理,故只需处理两个表达式。
x = a(mod m)
x = b(mod n)
km+a = b (mod n)
km = (a-b)(mod n)
利用扩展欧几里得算法求出k
k = k0(mod n/(n,m)) = k0 + h*n/(n,m)
x = km+a = k0*m+a+h*n*m/(n,m) = k0*m+a (mod n*m/(n,m))
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cstdlib>#include <utility>#include <vector>#include <queue>#include <map>#include <set>#define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)>(y)?(y):(x))#define INF 0x3f3f3f3f#define LL long longusing namespace std;LL m0, m1, a0, a1;LL Exgcd(LL a,LL b,LL &x,LL &y) // ax+by = (a,b){ if(b == 0) { x = 1; y = 0; return a; } LL x1,y1,x0,y0; x0=1; y0=0; x1=0; y1=1; x=0; y=1; LL r=a%b; LL q=(a-r)/b; while(r) { x=x0-q*x1; y=y0-q*y1; x0=x1; y0=y1; x1=x; y1=y; a=b; b=r; r=a%b; q=(a-r)/b; } return b;}int main(){ int n; while(scanf("%d", &n) != EOF) { scanf("%lld%lld", &m0, &a0); bool flag = 0; while(--n) { scanf("%lld%lld", &m1, &a1); LL x, y, tmp; LL d = Exgcd(m0, m1, x, y); x = (x%(m1/d)+m1/d)%(m1/d); tmp = ((a1-a0)%m1+m1)%m1; if(tmp%d != 0) flag = 1; x = x*(tmp/d)%(m1/d); a0 = (x*m0+a0+m0/d*m1)%(m0/d*m1); m0 = m0/d*m1; } if(flag) printf("-1\n"); else printf("%lld\n", a0); } return 0;}
POJ 2891 中国剩余定理的非互质形式
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。