You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
88 lines
2.5 KiB
88 lines
2.5 KiB
2 years ago
|
## [扩展中国剩余定理](https://www.luogu.com.cn/problem/P4777)
|
||
|
|
|
||
|
|
### 一、[题目描述]
|
||
|
|
|
||
|
|
给定 $k$ 组非负整数 $m_i, a_i$ ，求解关于 $x$ 的方程组的最小非负整数解。
|
||
|
|
$$\begin{cases} x \equiv a_1\ ({\rm mod}\ m_1) \\ x\equiv a_2\ ({\rm mod}\ m_2) \\ ... \\ x \equiv a_k\ ({\rm mod}\ m_k)\end{cases}$$
|
||
|
|
|
||
|
|
### 二、推导过程
|
||
|
|
首先，我们假定已经找到了前$k-1$个方程组的解：$ans+iM$,其中$\displaystyle M=\prod_{i=1}^{k-1} m_i $
|
||
|
|
|
||
|
|
|
||
|
|
那么我们现在需要找到一个非负整数，满足$ans+tM \equiv a_k (mod \ m_k)$，移项得
|
||
|
|
$tM \equiv a_k-ans(mod \ m_k)$
|
||
|
|
|
||
|
|
我们发现，这个形式与扩展欧几里得($exgcd$)的变形$ax \equiv c(mod \ b)$ 相同，于是令
|
||
|
|
|
||
|
|
$$
|
||
|
|
\large \left\{\begin{matrix}
|
||
|
|
A = M & \\
|
||
|
|
B = m_k & \\
|
||
|
|
C=|a_k-ans| & \\
|
||
|
|
X=t
|
||
|
|
\end{matrix}
|
||
|
|
\right.
|
||
|
|
$$
|
||
|
|
|
||
|
|
那么问题就转化为我们就要求不定方程$AX \equiv C(mod \ B)$ 的解。
|
||
|
|
|
||
|
|
而$exgcd(A,B,X,Y)$可以得到满足$AX+BY=gcd(A,B)$ 的一组解，将此式放在模$B$ 的意义下，就是$AX \equiv gcd(mod \ B)$.
|
||
|
|
|
||
|
|
所以若使得原同余方程组有解，必须有：$C$ 是$gcd(a,b)$的倍数。
|
||
|
|
|
||
|
|
那么我们要找的$t$就等于$X \cdot \frac{C}{gcd}$
|
||
|
|
那么满足前$k$个同余方程的解就是$ans=ans+t\cdot M$。
|
||
|
|
|
||
|
|
接下来更新$M=M\cdot m_k$,而在这里实际上$M$只需要求所有模数的最小公倍数即可，所以可以直接将其乘上$\frac{m_k}{gcd(m_k,M)}$,即$\frac{m_k}{gcd}$即可。
|
||
|
|
|
||
|
|
$Code$
|
||
|
|
```cpp {.line-numbers}
|
||
|
|
#include <cstdio>
|
||
|
|
#include <iostream>
|
||
|
|
using namespace std;
|
||
|
|
typedef long long ll;
|
||
|
|
const ll MAXN = 1e5 + 50;
|
||
|
|
void read(ll &x){/*Fast input, omit here*/}
|
||
|
|
ll n,a[MAXN],m[MAXN];
|
||
|
|
ll ans,M;
|
||
|
|
ll mult(ll a,ll b,ll p){
|
||
|
|
ll ans = 0;
|
||
|
|
while(b){
|
||
|
|
if(b & 1) ans = (ans + a) % p;
|
||
|
|
a = (a + a) % p;
|
||
|
|
b >>= 1;
|
||
|
|
}
|
||
|
|
return ans;
|
||
|
|
}
|
||
|
|
ll exgcd(ll a,ll b,ll &x,ll &y){
|
||
|
|
if(b == 0){
|
||
|
|
x = 1; y = 0;
|
||
|
|
return a;
|
||
|
|
}
|
||
|
|
ll gcd = exgcd(b, a%b, y, x);
|
||
|
|
y -= (a / b) * x;
|
||
|
|
return gcd;
|
||
|
|
}
|
||
|
|
ll solve(){
|
||
|
|
ans = a[1],M = m[1];
|
||
|
|
for(ll i = 2;i <= n;++i){
|
||
|
|
ll A = M, B = m[i], C =((a[i] - ans) % B + B) % B, x, y;
|
||
|
|
ll gcd = exgcd(A, B, x, y);
|
||
|
|
//耐心看………………ovo
|
||
|
|
if(C % gcd != 0) return -1;
|
||
|
|
x = mult(x, C / gcd, B);
|
||
|
|
ans += M * x;
|
||
|
|
M *= m[i] / gcd;
|
||
|
|
ans = (ans % M + M) % M;
|
||
|
|
}
|
||
|
|
return ans = (ans % M + M) % M;
|
||
|
|
}
|
||
|
|
int main(){
|
||
|
|
read(n);
|
||
|
|
for(ll i = 1;i <= n;++i){
|
||
|
|
read(m[i]), read(a[i]);
|
||
|
|
}
|
||
|
|
printf("%lld\n", solve());
|
||
|
|
return 0;
|
||
|
|
}
|
||
|
|
```
|