Hdu 1573 X问题 + Hdu 3579 Hello Kiki (模线性方程组-非互质中国剩余

2019-04-13 17:21发布

站内文章 / 模拟电子
9704 0 1697
关于模线性方程，可以参考我的上一篇博文。 以下叙述及证明转自：http://972169909-qq-com.iteye.com/blog/1266328 作者 KIDx  
问题描述：给出bi，ni的值，且n1, n2, n3,…, ni两两之间不一定互质，求Res的值？ 
解：采用的是合并方程的做法。 
这里将以合并第一第二个方程为例进行说明 
由上图前2个方程得(设k1、k2为某一整数)： 
 


Hdu 1573 X问题 #include #define i64 __int64 i64 Md[15],w[15],n; //w[]保存余数 i64 Extended_Euclid (i64 a,i64 b,i64 &x,i64 &y) {//扩展欧几里得算法,求ax+by=gcd(a,b)的一组解(x,y),d=gcd(a,b) i64 d; if (b==0) { x=1;y=0; return a; } d=Extended_Euclid(b,a%b,y,x); y-=a/b*x; return d; } i64 Chinese_Remainder (i64 w[],i64 Md[],int len) {//中国剩余定理不互质 bool flag=false; i64 n1=Md[0], b1=w[0],x,y; for (int i=1;i n) return 0; return (n-b1)/n1+1; //形成的解：b1, b1+n1, b1+2n1,..., b1+xni... } int main () { #ifdef ONLINE_JUDGE #else freopen("read.txt","r",stdin); #endif int T,i,m; scanf("%d",&T); while (T--) { scanf("%d%d",&n,&m); for (i=0;i
Hdu 3579 Hello Kiki  题意：n个m[i]，和n个a[i]，一个数对m[i]取模的值为a[i]，求这个数，其中m[i]之间不一定互质 #include #define i64 __int64 i64 Md[10],w[10]; //w[]保存余数 i64 Extended_Euclid (i64 a,i64 b,i64 &x,i64 &y) {//扩展欧几里得算法,求ax+by=gcd(a,b)的一组解(x,y),d=gcd(a,b) i64 d; if (b==0) { x=1;y=0; return a; } d=Extended_Euclid(b,a%b,y,x); y-=a/b*x; return d; } i64 Chinese_Remainder (i64 w[],i64 Md[],int len) {//中国剩余定理不互质 bool flag=false; i64 n1=Md[0], b1=w[0],x,y; for (int i=1;i

热门文章