基本应用：求 $n$ 个同余方程 $x \equiv r_i \pmod{m_i}$ 形成的方程组，求最小的 $x$ 。其中 $m_i$ 两两互质。
$\left{\begin{matrix}
x \equiv r_1 \pmod {m_1} \
x \equiv r_2 \pmod {m_2} \
x \equiv r_3 \pmod {m_3} \
\vdots \
x \equiv r_n \pmod {m_n}
\end{matrix}\right.$
设 $M=\textstyle \prod_{i=1}^nm_i,M_i=\dfrac{M}{m_i},M’_i \equiv M_i^{-1} \pmod {m_i}$
则 $x \equiv \textstyle\sum_{i=1}^nr_iM’_iM_i \pmod M$
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
| void exgcd(ll a,ll b,ll &x,ll &y) {
if(!b) x = 1,y = 0;
else {
exgcd(b,a % b,y,x);
y -= x * (a / b);
}
}
ll QuickMul(ll a,ll b,ll MOD) {
ll ans = 0;
while(b){
if(b&1) ans = (ans + a) % MOD;
a = (a + a) % MOD;
b >>= 1;
}
return ans;
}
int A[maxN];
int B[maxN];
ll M = 1;ll ans = 0;
int main() {
int K = read();
for(int i = 1; i<=K; i++) A[i] = read();
for(int i = 1; i<=K; i++) B[i] = read();
for(int i = 1; i<=K; i++) M *= B[i];
for(int i = 1; i<=K; i++) {
ll t = M / B[i];
ll x,y;
exgcd(t,B[i],x,y);
x = (x % B[i] + B[i]) % B[i];
ans = (ans + QuickMul(QuickMul(t,x,M),(A[i]+M)%M,M)) % M;
}
printf("%lld",(ans+M)%M);
return 0;
}
|