復(fù)習(xí)一下

擴(kuò)展中國(guó)剩余定理

• 首先考慮兩個(gè)同余方程
  \[ x \equiv a_1\; mod\; m_1\\ x \equiv a_2\; mod\; m_2 \]

• 化成另一個(gè)形式

\[ x = n_1 * m_1 + a_1\\ x = n_2 * m_2 + a_2 \]

• 聯(lián)立可得
  \[ n_1 * m_1 + a_1 = n_2 * m_2 + a_2\\ n_1 * m_1 - n_2 * m_2 = a_2 - a_1 \]
• 有解的前提是
  \[ \gcd(m_1, m_2) |(a_2 - a_1) \]
• 設(shè)
  \[ d = \gcd(m_1, m_2)\\ c = a_2 - a_1 \]
• 則
  \[ n_1 \frac{m_1}ze8trgl8bvbq - n_2 \frac{m_2}ze8trgl8bvbq = \frac{c}ze8trgl8bvbq\\ n_1 \frac{m_1}ze8trgl8bvbq \equiv \frac{c}ze8trgl8bvbq \ mod \ \frac{m_2}ze8trgl8bvbq \]
• 移項(xiàng)

\[ n_1 \equiv \frac{c}ze8trgl8bvbq * inv(\frac{m_1}ze8trgl8bvbq, \frac{m_2}ze8trgl8bvbq) \ mod\ \frac{m_2}ze8trgl8bvbq\\ n_1 = \frac{c}ze8trgl8bvbq * inv(\frac{m_1}ze8trgl8bvbq, \frac{m_2}ze8trgl8bvbq) + y_1 * \frac{m_2}ze8trgl8bvbq \]
然后\(n_1\)代入最上面的獅子可以得到

\[ x = (\frac{c}ze8trgl8bvbq * inv(\frac{m_1}ze8trgl8bvbq, \frac{m_2}ze8trgl8bvbq) + y_1 * \frac{m_2}ze8trgl8bvbq) * m_1 + a_1\\ x = m_1 * \frac{c}ze8trgl8bvbq * inv(\frac{m_1}ze8trgl8bvbq, \frac{m_2}ze8trgl8bvbq) + y_1 * \frac{m_2 m_1}ze8trgl8bvbq + a_1\\ x \equiv m_1 * \frac{c}ze8trgl8bvbq * inv(\frac{m_1}ze8trgl8bvbq, \frac{m_2}ze8trgl8bvbq) + a_1 \ mod \ \frac{m_2 m_1}ze8trgl8bvbq \]

• 然后就是個(gè)新方程了
• 當(dāng)然也適用于互質(zhì)情況

#include<cstdio> #include<algorithm> #include<cstring> #include<queue> #include<iostream> #define ll long long #define M 22 #define mmp make_pair using namespace std; int read() {int nm = 0, f = 1;char c = getchar();for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';return nm * f; }ll gcd(ll a, ll b) {return !b ? a : gcd(b, a % b); }ll exgcd(ll a, ll b, ll &x, ll &y) {if(!b){x = 1, y = 0;return a;}else{ll d = exgcd(b, a % b, x, y);ll tmp = x;x = y;y = tmp - a / b * y;return d;} }ll inv(ll a, ll p) {ll x, y;ll d = exgcd(a, p, x, y);if(d != 1) return -1;return (x % p + p) % p; } ll a[M], b[M], n; ll excrt() {ll a1 = a[1], m1 = b[1], a2, m2;for(int i = 2; i <= n; i++){a2 = a[i], m2 = b[i];ll c = a2 - a1, d = gcd(m1, m2);if(c % d) return -1;ll k = inv(m1 / d, m2 / d);m2 = m1 / d * m2;a1 = m1 * c / d % m2 * k + a1;m1 = m2;a1 = (a1 % m1 + m1) % m1; }return a1; }int main() {n = read();for(int i = 1; i <= n; i++) b[i] = read(), a[i] = read();cout << excrt() << "\n";return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/luoyibujue/p/10673305.html

總結(jié)

以上是生活随笔為你收集整理的「一本通 6.4 例 4」曹冲养猪(CRT)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。