中国剩余定理（CRT） 证明 互质与不互质

本文主要是介绍中国剩余定理（CRT） 证明 互质与不互质，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

中国剩余定理（CRT）

图来自博客：https://blog.csdn.net/u012717411/article/details/43168405

我对此做一些解释。

首先，（Mi，mi）=1表示它两互质

下面这个方程更有利于理解扩展欧几里德如何求解

是Mi模mi的逆元,

另一种好理解证明：

  

代码模板：

typedef long long ll;
void extend_Euclid(ll a, ll b, ll &x, ll &y)
{if(b == 0){x = 1;y = 0;return;}extend_Euclid(b, a % b, x, y);ll tmp = x;x = y;y = tmp - (a / b) * y;
}ll CRT(ll a[],ll m[],ll n)   //xi≡a[i]( mod m[i])
{ll M = 1;ll ans = 0;for(int i=1; i<=n; i++)M *= m[i];for(int i=1; i<=n; i++){ll x, y;ll Mi = M / m[i];extend_Euclid(Mi, m[i], x, y);ans = (ans + Mi * x * a[i]) % M;}if(ans < 0) ans += M;return ans;
}

经典例题：POJ 1006 Biorhythms

重点来了：

m[i]如果不互质呢，那就可以用改进的中国剩余定理了。

证明如下：

代码实现：

typedef long long ll;
ll gcd(ll a,ll b) { return b == 0 ? a : gcd(b, a % b); }
ll e_gcd (ll a, ll b, ll& x, ll& y)
{if (b == 0){x = 1, y = 0;return a;}ll ans = e_gcd (b, a % b, y, x);y -= a / b * x;return ans;
}
ll CRT(int a[], int m[], int n)
{ll Mi = m[1], ans = a[1];for (int i = 2; i <= n; ++i){ll mi = m[i], ai = a[i];ll x, y;ll gcd = e_gcd (Mi, mi, x, y);ll c = ai - ans;if (c % gcd != 0) return -1;ll M = mi / gcd;ans += Mi * ( ( (c /gcd*x) % M + M) % M);Mi *= M;}if (ans == 0) //当余数都为0{ans = 1;for (int i = 1; i <= n; ++i){ans = ans*m[i]/gcd(ans,(ll)m[i]);}}return ans;
}

经典例题：HDU 3579 Hello Kiki

这篇关于中国剩余定理（CRT） 证明 互质与不互质的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---