求解xx满足

{xr1 (mod m1)xr2 (mod m2)...xr3 (mod m3) \begin{cases} x &\equiv r_1 ~(mod~m_1) \\ x &\equiv r_2 ~(mod~m_2) \\ &...\\ x &\equiv r_3 ~(mod~m_3) \end{cases}

Solution

可以利用ex_gcd合并模线性方程组

假设现在我们合并前两个方程组:

{xr1 (mod m1)xr2 (mod m2) \begin{cases} x \equiv r_1 ~(mod~m_1) \\ x \equiv r_2 ~(mod~m_2) \end{cases}

展开得到:

{x=m1k1+r1x=m2k2+r2 \begin{cases} x =m_1 k_1 + r_1 \\ x =m_2 k_2 + r_2 \end{cases}

联立得到:

m1k1+r1=m2k2+r2 m_1 k_1 + r_1 = m_2 k_2 + r_2 m1k1m2k2=r2r1 m_1 k_1 - m_2 k_2 = r_2 - r_1

a=m1,b=m2,c=r2r1a=m_1, b = m_2, c = r_2 - r1,那么就变成了ax+by=cax+by=c的形式

用扩欧即可求出k1k_1的最小非负整数解(无解也很好判)

再把求得的解带入之前的方程即能得到x=x0x=x_0的一个特解

那么事实上这个x0x_0就能作为新的方程的RR了,而新的方程的MM很显然是lcm(m1,m2){lcm}(m_1,m_2)

我们知道k1k_1与其相邻解的间距为m2gcd(m1,m2)\frac{m_2}{\gcd(m1,m2)},又因为x=m1k1+r1x=m_1k_1+r_1,所以xx相邻解的间距为m1m2gcd(m1,m2)=lcm(m1,m2)\frac{m_1m_2}{\gcd(m_1,m_2)}={lcm}(m1,m2)

至此,我们就将两个方程组合并成新的一个方程xR(mod M)x\equiv R(mod~M)

不断重复上述过程,即能合并所有方程组了

Something

这里提一下一个一直没搞清楚的问题.

在用扩欧求最小非负整数解时,需要把gcd都除干净.

即要a/=gcd, b/=gcd, c/=gcd,这样才能求出最小非负整数解

这是因为对于ax+by=gcd(a,b)ax+by=\gcd(a,b)这个方程而言,相邻xx的解的间距其实是bgcd(a,b)\frac{b}{\gcd(a,b)},而并非bb

但是,通过写错还能A掉的实践经验可以得出在合并模线性方程组时,除不除gcd得到的结果是一样的.


(注:以下内容为本人研究写错的做法最后答案是对的的原因,与此算法没有什么太大关系)

考虑原方程m1k1m2k2=gcd(m1,m2)m_1k_1-m_2k_2=gcd(m_1,m_2)的解k1k_1与除完gcd之后的方程m1gcdk1m2gcdk2=1\frac{m_1}{gcd}k_1-\frac{m_2}{gcd}k_2=1的解k1k_1'

显然,k1k_1正确的间距是m2gcd\frac{m_2}{gcd},但在原方程直接求非负整数解时,间距被误算成了m2m_2

那么k1k_1k1k_1'的差Δ\Delta会是m2gcd\frac{m_2}{gcd}的若干倍

带入x=m1k1+r1x=m_1k_1+r_1中可以发现最终正确答案xx与错误答案xx'的差会是m1m2gcd\frac{m_1m_2}{gcd}的若干倍,即是lcm(m1,m2){ lcm}(m_1,m_2)的若干倍

所以最后在模lcm(m1,m2){ lcm}(m_1,m_2)意义下这两个答案是相同的

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }

inline void proc_status()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) <<endl;
}

inline LL read ()
{
LL sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

const int Maxn = 1e5 + 10;

int N;
LL A[Maxn], B[Maxn];

inline LL ex_gcd (LL a, LL b, LL &x, LL &y)
{
if (!b) { x = 1, y = 0; return a; }
LL g = ex_gcd(b, a % b, x, y);
LL tmp = x;
x = y, y = tmp - a / b * y;
return g;
}

inline LL Mult (LL a, LL b, LL Mod)
{
a = (a % Mod + Mod) % Mod;
b = (b % Mod + Mod) % Mod;
LL ans = 0;
while (b)
{
if (b & 1) ans = (ans + a) % Mod;
a = (a + a) % Mod;
b >>= 1;
}
return ans;
}

inline void Solve ()
{
for (int i = 2; i <= N; ++i)
{
LL x, y;
LL a = A[i], b = A[1], c = B[1] - B[i], g = __gcd(a, b);
if (c % g) return ;
a /= g, b /= g, c /= g;
ex_gcd (a, b, x, y);
x = ((Mult(x, c, b)) % b + b) % b;
A[1] = A[i] / __gcd(A[1], A[i]) * A[1];
B[1] = (B[i] + A[i] * x) % A[1];
}
cout<<B[1]<<endl;
}

inline void Input ()
{
N = read();
for (int i = 1; i <= N; ++i) A[i] = read(), B[i] = read();
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
#endif
Input();
Solve();
return 0;
}