同余方程[组] 乘法模逆元 中国剩余定理【模板】

2019-04-13 13:55发布

站内文章 / 模拟电子
15679 0 1027
同余定义： 给定正整数M，若用M去除两个整数 a 和 b 所得余数相同，称 a 和 b 对模 m 同余，记作 a ≡ b (mod m)，并称该式为同余式；否则，称 a 和 b 对模 m 不同余。 同余定理： 1.a ≡ b (mod m)，当且仅当m | (a - b)。 2.a ≡ b (mod m)，当且仅当存在整数 k，使得a = b + k*m。 3.a ≡ a (mod m)。 4.若 a ≡ b (mod m)，则 b ≡ a (mod m)。 5.若 a ≡ b (mod m)，b ≡ c (mod m)，则 a ≡ c (mod m). 6.若 a、b、c 是整数，m 是正整数，且 a ≡ b (mod m)，则 a + c ≡ b + c (mod m)；a - c ≡ b - c (mod m)；a*c ≡ b*c (mod m)。 7.设 a、b、c、d 为整数，m 为正整数，若 a ≡ b (mod m)，则 a*x + c*y = b*x + d*y (mod m)，其中 x，y 为任意整数； a*c ≡ b*d (mod m)； a^n ≡ b^n (mod m)，其中n > 0； f(a) ≡ f(b) (mod m)，其中 f(x) 为任一整系数多项式。 8.设a、b、c、d为整数，m为正整数，则： 若 a ≡ b (mod m)，且d | m，则 a ≡ b (mod d)； 若 a ≡ b (mod m)，则gcd(a，m) ≡ gcd(b，m)； a ≡ b (mod mi) (1 <= i <= n)同时成立，当且仅当 a ≡ b (mod lcm(m1，m2，…，mn))； 9.若 a*c ≡ b*c (mod m)，且gcd(c，m) = d，则 a ≡ b (mod m/d)。
扩展欧几里得，求一组解x，y，使得gcd(a，b)  = d = a * x + b * y void ExGcd(int a,int b,int &d,int &x,int &y) { if(b == 0) { x = 1; y = 0; d = a; } else { ExGcd(b,a%b,d,y,x); y -= x*(a/b); } } 扩展欧几里得，求所有解x，y，使得c = a * x + b * y bool ModeEqual(int a,int b,int c) //解a*x + b*y = c;a*x ≡ c(mod b) { int x,y,d,x0; ExGcd(a,b,d,x,y); if(c%d) return false; //无解 x0 = x * (c/d) % b; for(int i = 1; i < d; ++i) //输出所有解 printf("%d ",(x0+i*(b/d))%b); return true; } 扩展欧几里得，求a关于n的逆元a^-1，使得a * a^-1 ≡ 1(mod n) int ModInverse(int a,int n,int &d,int &x,int &y) { ExGcd(a,n,d,x,y); if(1 % d != 0) return -1; //不存在模逆元 int ans = x/d < 0 ? x/d + n : x/d; return ans; //返回模逆元a^-1 } 扩展欧几里得，求解x，满足同余方程组x ≡ Ri(mod Ai) int ModEquals(int N) //解方程组x ≡ Ri(mod Ai) { int a,b,d,x,y,c,A1,R1,A2,R2; bool flag = 1; //标记是否有解 scanf("%d%d",&A1,&R1); for(int i = 1; i < N; ++i) { scanf("%d%d",&A2,&R2); a = A1, b = A2, c = R2 - R1; ExGcd(a,b,d,x,y); if(c % d != 0) flag = 0; int t = b/d; x = (x*(c/d)%t + t) % t; R1 = A1 * x + R1; A1 = A1 * (A2 / d); } if( !flag ) R1 = -1; return R1; //求出解，-1表示无解 } 扩展欧几里得，求解x，满足高次同余方程A^x ≡ B(mod C) #define LL __int64 const int MAXN = 65535; struct HASH { int a; int b; int next; }Hash[MAXN*2]; int flag[MAXN+66]; int top,idx; void ins(int a,int b) { int k = b & MAXN; if(flag[k] != idx) { flag[k] = idx; Hash[k].next = -1; Hash[k].a = a; Hash[k].b = b; return; } while(Hash[k].next != -1) { if(Hash[k].b == b) return; k = Hash[k].next; } Hash[k].next = ++top; Hash[top].next = -1; Hash[top].a = a; Hash[top].b = b; } int Find(int b) { int k = b & MAXN; if(flag[k] != idx) return -1; while(k != -1) { if(Hash[k].b == b) return Hash[k].a; k = Hash[k].next; } return -1; } int GCD(int a,int b) { if(b == 0) return a; return GCD(b,a%b); } void ExGcd(int a,int b,int &d,int &x,int &y) { if(b == 0) { x = 1; y = 0; d = a; } else { ExGcd(b,a%b,d,y,x); y -= x*(a/b); } } int Inval(int a,int b,int n) { int x,y,d,e; ExGcd(a,n,d,x,y); e = (LL)x*b%n; return e < 0 ? e + n : e; } int PowMod(LL a,int b,int c) { LL ret = 1%c; a %= c; while(b) { if(b&1) ret = ret*a%c; a = a*a%c; b >>= 1; } return ret; } int BabyStep(int A,int B,int C) //解A^x ≡ B(mod C) { top = MAXN; ++idx; LL buf = 1%C,D = buf,K; int d = 0,temp,i; for(i = 0; i <= 100; buf = buf*A%C,++i) { if(buf == B) return i; } while((temp = GCD(A,C)) != 1) { if(B % temp) return -1; ++d; C /= temp; B /= temp; D = D*A/temp%C; } int M = (int)ceil(sqrt((double)C)); for(buf = 1%C,i = 0; i <= M; buf = buf*A%C,++i) ins(i,buf); for(i = 0,K = PowMod((LL)A,M,C); i <= M; D = D*K%C,++i) { temp = Inval((int)D,B,C); int w; if(temp >= 0 && (w = Find(temp)) != -1) return i * M + w + d; } return -1; //无解 } 中国剩余定理： 简单描述： 已知 n%3=2，n%5=3，n%7=2，求n。
因为 n%3=2，n%5=3，n%7=2 且 3，5，7互质 （互质可以直接得到这三个数的最小公倍数）
令 x = n % 3 = 2，y = n%5=3，z = n%7=2。 
    使5*7*a 被3除余1，有35×2=70，即 a = 2； 
    使3*7*b 被5除余1，有21×1=21，即 b = 1； 
    使3*5*c 被7除余1，有15×1=15，即 c = 1。 
那么 n =(70×x+21×y+15×z) % lcm(3，5，7) = 23 这是n的最小解
其中，a 为 (5*7)^-1 mod 3，b 为 (3*7)^-1 mod 5，c 为 (3*5)^-1 mod 7。
 一般描述： 若m1，m2，m3，…，mr是两两互素的正整数，则同余方程组  x ≡ a1 (mod m1)  x ≡ a2 (mod m2)
  x ≡ a3 (mod m3)
 ……  x ≡ ar (mod mr)
 有模M = m1*m2*m3*…*mr的唯一解，即为中国剩余定理。 解法： 令Mi = M/mi，因为m1，m2，m3，…，mr两两互素，因此 gcd(Mi，mi) = 1，即 MiPi ≡ 1 (mod mi)，那么解为 a1*M1*P1 + a2*M2*P2 + a3*M3*P3 + … + ar*Mr*Pr。 得到最小非负数解的算法： int m[110],a[110]; //m[]和a[]对应x ≡ ai (mod mi) void ExGcd(int a,int b,int &d,int &x,int &y) { if(b == 0) { x = 1; y = 0; d = a; } else { ExGcd(b,a%b,d,y,x); y -= x*(a/b); } } int China(int r) // r为同于方程组个数 { int M = 1,Mi,x0,y0,d,ans = 0; for(int i = 1; i <= r; ++i) M *= m[i]; for(int i = 1; i <= r; ++i) { Mi = M / m[i]; ExGcd(Mi,m[i],d,x0,y0); //调用扩展欧几里得，见之前 ans = (ans + Mi*x0*a[i]) % M; } if(ans < 0) ans += M; return ans; } 中国剩余定理推论： 1.若a，b是正整数，那么gcd(2^a-1，2^b-1) = 2^gcd(a，b) - 1. 2. 2*a - 1，2*b - 1是互素的，当且仅当正整数a，b是互素的。



热门文章