扩展GCD 中国剩余定理(CRT) 乘法逆元模版

2019-04-14 17:08发布

站内文章 / 模拟电子
9350 0 1452
extend_gcd： 已知 a,b (a>=0,b>=0) 求一组解 (x,y) 使得 (x,y)满足 gcd(a,b) = ax+by 下面代码中d = gcd(a,b)，顺便求出gcd 可以扩展成求等式 ax+by = c,但c必须是d的倍数才有解,即 (c%gcd(a,b))==0
注意求出的 x,y 可能为0或负数 =================================== 乘法逆元： a*b %n == 1 已知 a, n, 求b 就是乘法逆元 ===================================
中国剩余定理： 给定方程组: x%a[0] = m[0] x%a[1] = m[1] ··· x%a[n-1] = m[n-1] 求变量x 的值 m必须互质 当m不互质时用合并方程的做法： （合并方程的原因：当我们把n条方程合并成1条时就是extend能求的了，extend能求一条方程的解
问题描述：给出bi，ni的值，且n1, n2, n3,…, ni两两之间不一定互质，求Res的值？ 
解：采用的是合并方程的做法。 
这里将以合并第一第二个方程为例进行说明 
由上图前2个方程得(设k1、k2为某一整数)： 
所以我们简化一下结论： 已知方程组（b1,b2,n1,n2是已知量）： res%b1 = n1 res%b2 = n2 -> 合并两条方程得到： res % ( (n1*n2)/d ) = b1+n1*( K%(n2/d)) 其中K = (k1*(b2-b1)/d) % (n2/d); 
其中d = gcd(n1,n2); 其中k1： k1*n1 - k2*n2 = b2-b1 k1,d 可以直接由extend_gcd得到 extend_gcd(n1,n2,d,k1,k2); (b2-b1)%d == 0 说明extend跑出的k1是一个解，否则说明不存在满足解的k1 注意求K时：为了得到最小非负整数K，所以用一个取模的技巧 K = (K%mod+mod)%mod; 例题及题解：点击打开链接 ================================== 若 a == b (mod n) 能推出下面2条等式 1： (a+c) == b+c (mod n) 2：ac == bc (mod n) （但 ac==bc(mod n) 不能推出 a==b(mod n)）
#include #include #include #include #include #include #include #include #include using namespace std; #define ll __int64 ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a%b); } void extend_gcd (ll a , ll b , ll& d, ll &x , ll &y) { if(!b){d = a; x = 1; y = 0;} else {extend_gcd(b, a%b, d, y, x); y-=x*(a/b);} } ll china(ll l, ll r, ll *m, ll *a){ //下标[l,r] 方程x%m=a; ll lcm = 1; for(ll i = l; i <= r; i++)lcm = lcm/gcd(lcm,m[i])*m[i]; for(ll i = l+1; i <= r; i++) { ll A = m[l], B = m[i], d, x, y, c = a[i]-a[l]; extend_gcd(A,B,d,x,y); if(c%d)return -1; ll mod = m[i]/d; ll K = ((x*c/d)%mod+mod)%mod; a[l] = m[l]*K + a[l]; m[l] = m[l]*m[i]/d; } if(a[l]==0)return lcm; return a[l]; }

热门文章