1.前言
扩展中国剩余定理好绕啊,很多地方取模都有讲究,所以写篇笔记来方便自己复习。
2.问题
给出一个二元组序列 \(\{(b_i,m_i)\}\),要求找出一个 \(Q\),满足要求:
\[\forall (b_i,m_i),Q \equiv b_i \pmod {m_i} \]3.思路
- 找到一个都满足的解,将余数修改为这个解(记录下一个解)
- 将两个同余方程的模数修改为 \(lcm (m_i,m_j)\)(合并, \(lcm (m_i,m_j\) 即为新方程的周期)
- 继续向下合并
具体式子:
合并两个同余方程
\(Q \equiv b_i (mod m_i)\)
\(Q \equiv b_j (mod m_j)\)
合并为:
求出 \(x, y\),满足要求\(x * m_i + b_i = y * m_j + b_j\)
\(Q \equiv b_i + x * m_i \pmod {lcm (m_i, m_j)}\)
4.实现
思路相当简单,但是为了防止溢出,我们需要及时的取模,而实现的取模特别有讲究。
1.求解 \(x,y\) 的过程
由于我们合并的最终式子只有 \(x\),所以我们可以不考虑 \(y\) 的值
条件为 \(x * m_i + b_i = y * m_j + b_j\),等价于 \(x * m_i \equiv b_j - b_i \pmod {m_j}\)
所以 \(b_j - b_i\) 可以对 \(m_j\) 取模
令 \(p = delta = \frac {lcm (m_i,m_j)}{m_i}\)
则 \(x\) 可以对 \(p\) 取模
2.合并的过程
令 \(M = lcm (m_i, m_j)\),而 \(Q \equiv b_i + x * m_i \pmod {M}\)
则 \(Q(b_i + x* m_i)\) 可以对 \(M\) 取模
5.参考代码
#include <cstdio>
#include <iostream>
using namespace std;
#define LL long long
#define ULL unsigned long long
template <typename T> void read (T &x) { x = 0; T f = 1;char tem = getchar ();while (tem < '0' || tem > '9') {if (tem == '-') f = -1;tem = getchar ();}while (tem >= '0' && tem <= '9') {x = (x << 1) + (x << 3) + tem - '0';tem = getchar ();}x *= f; return; }
template <typename T> void write (T x) { if (x < 0) {x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0'); }
template <typename T> void print (T x, char ch) { write (x); putchar (ch); }
template <typename T> T Max (T x, T y) { return x > y ? x : y; }
template <typename T> T Min (T x, T y) { return x < y ? x : y; }
template <typename T> T Abs (T x) { return x > 0 ? x : -x; }
LL gcd (LL x, LL y) {
if (y == 0) return x;
else return gcd (y, x % y);
}
LL lcm (LL x, LL y) {
return x / gcd (x, y) * y;
}
void exgcd (LL a, LL b, LL &x, LL &y) {
if (b == 0) {
x = 1; y = 0;
return ;
}
exgcd (b, a % b, y, x);
y -= (a / b) * x;
}
LL mul (LL x, LL y, LL Mod) {
LL res = 0;
while (y) {
if (y & 1) res = (res + x) % Mod;
x = (x + x) % Mod; y >>= 1;
}
return res;
}
LL solve (LL a, LL b, LL c) {
LL _gcd = gcd (a, b);
c = (c % b + b) % b;
if (c % _gcd != 0) return -1;
LL x, y;
exgcd (a, b, x, y);
LL p = b / _gcd;
x = (x % p + p) % p;
x = mul (x, c / _gcd, p);
return x;
}
const int Maxn = 1e5;
int n;
struct Eq {
LL Mod, b;
}a[Maxn + 5];
int main () {
read (n);
for (int i = 1; i <= n; i++) {
read (a[i].Mod); read (a[i].b);
a[i].b %= a[i].Mod;
}
LL Mod = a[1].Mod, b = a[1].b;
for (int i = 2; i <= n; i++) {
LL res = solve (Mod, a[i].Mod, a[i].b - b);
if (res == -1) {
printf ("No Answer!");
return 0;
}
LL M = lcm (Mod, a[i].Mod);
b = (b + mul (res, Mod, M)) % M;
Mod = M;
}
printf ("%lld", b);
return 0;
}