基础数论
前置芝士：
等比数列求和：
$S_n=a_0\frac{1-q^n}{1-q}$
质数与约数：
整除与约数
设 $n$ 为非负整数，$d$ 为正整数，若 $\frac{n}{d}$ 为整数，则称 $d$ 整除 $n$，记为$d\mid n$。此时，则称 $d$ 是 $n$ 的约数，或因数、因子；称 $n$ 为 $d$ 的倍数。
质数与合数的定义：
对于 $n \geq 2$ ，若 $\forall 1<i<n,i\nmid n$ ，则称 $n$ 为质数，否则 $n$ 为合数。
质数判定：
试除法：
单次时间复杂度 $O(\sqrt n\ )$
bool is_prime(int n) {
if(n < 2)
return false;
for(int i=2; i<= sqrt(n); ++i) {
if(n % i == 0)
return false;
}
return true;
}
质数筛法一：
从 $2$ 到 $n$ 枚举整数 $i$，标记大于 $i$ 且不大于 $n$ 的 $i$ 的倍数。枚举到 $i$ 时，若 $i$ 没有被标记过，则 $i$ 为质数。
时间复杂度 $O(\sum_{i=1}^n \frac{n}{i})=O(n\log n)$
void found_prime() {
memset(vis, 0, sizeof(vis));
vis[0] = 1; vis[1] = 1; // 特殊处理 0 和 1
for(int i=2; i<=n; ++i) {
for(int j=i*2; j<=n; j+=i)
vis[j] = 1; // 标记合数
}
}
埃氏筛：
只需要枚举质数的倍数就可以标记到所有合数了。实际上对于每个质数 $p$ 而言，小于$p^2$ 的 $p$ 的倍数在扫描到更小的质数时就已经被标记过了。
从 $2$ 到 $n$ 枚举整数 $i$，若 $i$ 是质数，则把 $i^2$ , $(i+1) \times i$, $\cdots$, $\lfloor \frac{n}{i}\rfloor \times i$ 标记为合数。枚举到 $i$ 时，若 $i$ 没有被标记过，则 $i$ 为质数。
时间复杂度 $O(\sum_{pr[i]\leq n}\frac{n}{pr[i]})=O(n\log\log n)$
void found_prime() {
memset(vis, 0, sizeof(vis));
vis[0] = 1; vis[1] = 1; // 特殊处理 0 和 1
for(int i=2; i<=n; ++i) {
if(!vis[i]) { // i 为质数
for(int j=i*i; j<=n; j+=i)
vis[j] = 1; // 标记合数
}
}
}
线性筛：
用每一个合数的最小质因子来标记这个合数。时间复杂度 $O(n)$
int pr[N],cnt;
bool vis[N];
void init(){
int n=1e5+50;
for(int i=2;i<=n;i++){
if(!vis[i]){pr[++cnt]=i;}
for(int j=1;j<=cnt&&i*pr[j]<=n;j++){
vis[i*pr[j]]=1;
if(i%pr[j]==0)break;
}
}
}
区间筛：(埃氏筛)
const int maxn = 1e6+10;
typedef long long LL;
bool is_prime[maxn]; //标记a~b范围内的质数
bool is_prime_small[maxn]; //标记 1~sqrt(n)范围内的所有质数
LL a, b;
//对区间[a, b]内的整数执行筛法，is_prime[i-a]=true表示i是素数
void found_prime()
{
for(LL i=0; i*i<=b; ++i)
is_prime_small[i] = true;
is_prime_small[1] = false;
for(LL i=0; i<=b-a; ++i)
is_prime[i] = true;
for(LL i=2; i*i<=b; ++i) {
if(is_prime_small[i]) { // i是质数
for(LL j=i*i; j*j<=b; j+=i) // 标记 sqrt(b) 以内的i的倍数
is_prime_small[j] = false;
for(LL j = max(2LL, (a+i-1)/i) * i; j<=b; j+=i) //标记[a, b]中i的倍数
is_prime[j-a] = false;
}
}
}
算术基本定理:
任何一个大于 1 的正整数都能唯一分解为若干个质数的乘积。
设 $n\geq2$ 为整数，有唯一的分解式：
$$
n=p_1^{c_1}\times p_2^{c_2}\times \cdots\times p_m{c_m}=\prod_{i=1}mp_i^{c_i}
$$
其中 $c_i$ 都是正整数，$p_i$ 都是质数，且满足 $p_1\leq p_2\leq...\leq p_m$
根据算术基本的定理，对于任意一个大于 $2$ 的整数 $n$，他的正约数集合可以写作：
$$
{p_1^{b_1}\times p_2^{b_2}\times \cdots\times p_m^{b_m}} (0\leq b_i\leq c_i)
$$
推论一： $n$ 的正约数个数为：
$$
(c_1+1)\times (c_2+1)\times \cdots\times (c_m+1)=\prod_{i=1}^m(c_i+1)
$$
推论二： $n$ 的所有正约数之和为：
$$
(1+p_1+p_12+...+p_1)\times\cdots\times (1+p_m+p_m2+...+p_m)=\prod_{i=1}m\sum_{j=0}p_i^j
$$
求解正约数集合：
试除法 求 $n$ 的正约数：
时间复杂度 $O(\sqrt n )$
int divisor[10010], cnt = 0;
for(int i=1; i<=sqrt(n); ++i) {
if(n % i == 0) {
divisor[++cnt] = i;
if(i != n/i) divisor[++cnt] = n/i;
}
}
推论：一个整数 $n$的正约数个数最多不超过 $2\times \sqrt n$ 个
倍数法 求$1\sim n$的正约数：
先枚举 $1 \sim n$ 中的每一个数作为约数 $d$，再在 $1\sim n$ 寻找 $d$ 的倍数即可。时间复杂度 $O(n+\frac{n}{2}+\cdots+\frac{n}{n})=O(n\log n)$
vecotr<int> divisor[500010];
for(int i=1; i<=n; ++i) { // 先枚举约数 i
for(int j=1; j<=n/i; ++j) //枚举 i 在 1~n 范围内的倍数 i × j
divisor[i*j].push_back(i); // i 是 i × j 的约数
}
推论：$1\sim n$ 的约数个数总和大约为 $n\log n$ 个。
${\rm gcd}$ :
$\forall a,b\in \mathbb{N},d\in \mathbb{N^{*}}$ 若 $d\mid a\ &\ d\mid b$ 则称 $d$ 为 $a,b$ 的公约数。
$a,b$ 的公约数中最大的称为 $a,b$ 的最大公约数，记为 $\gcd(a,b)$。
性质:
- $\gcd(a,b)=\gcd(b,a)$
- 对于 $\forall a,b\in \mathbb{N} $ 若 ${\rm gcd}(a,b)=1$ 则称 $a,b$ 互质。
- 由于任何正整数都是 $0$ 和 $0$ 的公约数，故 $\gcd (0,0)$ 不存在。
- 对于 $\forall a\in \mathbb{N^{*}}$ ，有 $\gcd(a,a)=a,\gcd(a,0)=a$ 。
- $\forall k\in \mathbb{Z}$，有 $\gcd(k\times a,k\times b)=k\times \gcd(a,b)$ 。
更相减损术：
$\forall a,b\in \mathbb{N^{*}}\ &\ a\geq b$ 有 $\gcd(a,b)=\gcd(b,a-b)=\gcd(a,a-b)$
$\forall d\mid a\ &\ d\mid b$，有 $a=k_1\times d,b=k_2\times d$ ，则 $(a-b)=(k_1-k_2)\times d$ ，所以 $d$ 也是 $b,a-b$ 的公约数，所以 $\gcd(a,b)=\gcd(b,a-b)$ 。
辗转相除法：
$\forall a,b\in \mathbb{N^{*}}\ &\ b!=0$ 有 $\gcd(a,b)=\gcd(b,a\bmod b)$
- 若 $a<b$ ，则 $\gcd(b,a\bmod b)=gcd(b,a)=gcd(a,b)$
- 若 $a\geq b$ ，设 $a=q\times b+r$ ，其中 $0\leq r <b$ 。$r=a\bmod b$ 。有 $a=k_1\times d,q\times b=k_2\times d$ ，则 $r=(a-q\times b)=(k_1-k_2)\times d$ ，因此 $d$ ，也是 $b,r$ 的公约数，故 $\gcd(a,b)=\gcd(b,a\bmod b)$
代码：
int gcd(int a, int b) {
while(b > 0 ) {
int x = a % b;
a = b;
b = x;
}
return a;
}
递归：
int gcd(int a, int b) {
return b ? gcd(b, a%b) : a;
}
最大复杂度 $O(\log(a+b))$
${\rm lcm}$：
$\forall a,b\in\mathbb{N^{*}},m\in \mathbb{N}$ 若 $a\mid m\ &\ b\mid m$，则称 $m$ 为 $a$ 和 $b$ 的公倍数。
$a,b$ 的公倍数中最小的称为 $a,b$ 的最小公倍数，记为 ${\rm lcm}(a,b)$ 。
$$
{\rm lcm}(a,b)=\frac{a\times b}{\gcd(a,b)}
$$
实际代码中： ${\rm lcm(a,b)=\frac{a}{\gcd(a,b)}\times b}$
整除分块：
例题：
已知 $f(n) =\sum\limits_{i = 1 }^{n}\left\lfloor\frac{n}{i}\right\rfloor$，给定 $n$，求 $f(n)$ 的值。
固然可以 $O(n)$ 暴力，但显然会$TLE$。
计算一下前几项的值之后可以发现$\left \lfloor \frac{n}{i} \right \rfloor$ 的取值在连续的一段区间内是相同的，那么就可以将其分为若干块分别进行计算。
先让 $l$ 为区间的左端点，那么这块的值都为 $k = \left\lfloor\frac{n}{l}\right\rfloor$ ， $r=max(i)=\left\lfloor\frac{n}{k}\right\rfloor$。将 $k$ 代入，得到 $r=\left\lfloor\frac{n}{\left\lfloor\frac{n}{l}\right\rfloor}\right\rfloor$。这样每一块的左右端点都能用确定的式子得到了。这样分块的值就为单值 $\times $ 区间长度，即 $k\times (r-l+1)$ 。
模板：
ll division_block(ll n){
ll res = 0;
for(ll l = 1, r; l <= n; l = r + 1){
r = n / (n / l);
res += n / l * (r - l + 1);
}
return res;
}
欧拉函数：
定义：
欧拉函数是指 $1 \sim N$ 中与 $N$ 互质的数的个数，记为 $\varphi(N)$。
即
$$
\varphi(x)=\sum_{i=1}^x[{\rm gcd}(i,x)==1]
$$
特别的 $\varphi(1)=1$
性质：
1.若 $x$ 为质数, $\varphi(x)=x-1$。
质数除了他本身都与他互质。
2.$\forall n>1,1\sim n$ 中与 $n$ 互质的数的和为 $n\times \varphi(n)/2$ 。
因为 ${\rm gcd}(n,x)=={\rm gcd}(n,n-x)$ ，所以与 $x$ 不互质的数 $x,n-x$ 成对出现，平均值为 $\frac{n}{2}$ ，所以与 $n$ 互质的数的平均值也是 $\frac{n}{2}$ ，而这样的数共有 $\varphi(n)$ 个，故得性质2。
3.若 $x=p^k(p为质数)$ ，则 $\varphi(x)=(p-1)\times p^{k-1}$。
发现所有 $p$ 的倍数都与 $x$ 不互质，其他数都与 $x$ 互质，而 $p$ 的倍数共有 $p^{k-1}$ 个(包括 $x$ )。
故$\varphi(x)=pk-p=(p-1)\times p^{k-1}$
4.若 $p,q$ 互质,则 $\varphi(p\times q)=\varphi(p)\times \varphi(q)$ ，即欧拉函数为积性函数。
如果 $a$ 与 $p$ 互质 $(a<p)$ ， $b$ 与 $p$ 互质 $(b<q)$ ， $c$ 与 $pq$ 互质 $(c<pq)$ ，则 $c$ 与数对 $(a,b)$ 是一一对应的。
符合条件的 $a$ 有 $\varphi(p)$ 种， $b$ 有 $\varphi(q)$ 种， 则所对应的 $(a,b)$ 数对有 $\varphi(p)\varphi(q)$ 种。而符合条件的 $c$ 有 $\varphi(pq)$ 种。
所以 $\varphi(pq)=\varphi(p)\times \varphi(q)$
5.对于一正整数 $x=p_1^{c_1}\times p_2^{c_2}\times ...\times p_n^{c_n}$ 有
$$
\varphi(x)=x\times \prod_{i=1}^{n}(1-\frac{1}{p_i})
$$
证明：
$$
\varphi(x)=\prod_{i=1}n\varphi(p_i)=\prod_{i=1}^n(p_i-1)\times p_i{c_i-1}=\prod_{i=1}np_i{k_i}\times(1-\frac{1}{p_i})=x\prod_{i=1}n(1-\frac{1}{p_i})
$$
6.若 $p$ 为 $x$ 的质因数，则 $\varphi(x\times p)=\varphi(x)\times p$
$$
\varphi(x\times p)=x\times \prod_{i=1}^n(1-\frac{1}{p_i})\times p=\varphi(x)\times p\
(p\in [p_i])
$$
7.若质数 $p$ 不是 $x$ 的因数，则 $\varphi(x\times p)=\varphi(x)\times (p-1)$
$$
\varphi(x\times p)=\varphi(x)\times \varphi(p)=\varphi(x)\times(p-1)
$$
$$
\sum_{d\mid n}\varphi(d)=n
$$
设 $f(n)=\sum_{d\mid n}\varphi(d)$
$\therefore f(a\times b)=\sum_{d\mid ab}\varphi(d)$
$当{\rm gcd}(a,b)=1时:$ ${\rm gcd}(\forall d_i\mid a,\forall d_i\mid b )=1$
$\therefore \sum_{d\mid ab}\varphi(d)=\sum_{d\mid a}\varphi(d)\times \sum_{d\mid b}\varphi(d)$
即 $f(a\times b)=f(a)\times f(b)$
$\therefore f(p^m)=\sum_{f\mid pm}\varphi(d)=\sum_{i=0}m\varphi(pi)=1+\sum_{i=0}(p-1)\times p^i(p为质数)$
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ =1+(p-1)\times (1+p+\cdots+p^{m-1})$
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ =1+(p-1)\times \frac{1-pm}{1-p}=pm$$\therefore f(pm)=pm$
$\therefore f(n)=f(\prod_{i=1}np_i)=\prod_{i=1}nf(p_i)=\prod_{i=1}np_i=n$
$\therefore \sum_{d\mid n}\varphi(d)=n$
代码：
1.求解单个欧拉函数：利用性质 $5$ ，时间复杂度 $O(\sqrt n)$ 。
int phi(int n) {
int ans = n;
int t = sqrt(n);
for(int i=2; i<=t; ++i) {
if(n%i == 0)
ans = ans/i*(i-1);
while(n%i == 0) n /= i;
}
if(n > 1) ans = ans/n/(n-1);
return ans;
}
- 埃氏筛求 $1\sim n$的欧拉函数值，时间复杂度 $O(n \log n)$
void found_euler(int n) {
for(int i=1; i<=n; ++i) phi[i] = i;
for(int i=2; i<=n; ++i) {
if(phi[i] == i) { // i为质数
for(int j=i; j<=n; j+=i) // 给包含质因子i的数字，乘上 (1-1/i)
phi[j] = phi[j]/i*(i-1);
}
}
}
3.欧拉筛求 $1\sim n$ 的欧拉函数值，时间复杂度 $O(n)$
int phi[N],pr[N],cnt;
bool vis[N];
void init(){
int n=1e5+50;
phi[1]=1;
for(int i=2;i<=n;i++){
if(!vis[i]){pr[++cnt]=i,phi[i]=i-1;}
for(int j=1;j<=cnt&&pr[j]<=n/i;j++){
vis[i*pr[j]]=1;
phi[i*pr[j]]=phi[i]*((i%pr[j])?pr[j]-1:pr[j]);
if(i%pr[j]==0)break;
}
}
}
模运算与逆元：
取模定义：
$$
a\bmod n\begin{cases}
a-\lfloor\frac{a}{n}\rfloor\times n \ \ \ \ \ a\geq0\
-(-a\bmod n)\ \ \ a<0
\end{cases}
$$
取模基本性质：
设 $a_0=a\bmod n,b_0=b\bmod n$
- $(a+b)\bmod n=((a\bmod n)+(b\bmod n))\bmod n$
$a+b\equiv a_0+b_0(\bmod n)$
-
$(a\times b)\bmod n=((a\bmod n)\times (b\bmod n))\bmod n$
$a\times b\equiv a_0\times b_0(\bmod n)$
-
对于任意正整数 $k$ ，有 $a\bmod n=(a\bmod kn)\bmod n$
-
若 $k \mid a$，有 $\frac{a}{k}\ mod\ n=\frac{a\ \bmod \ kn}{k}$
设 $\frac{a}{k}=x$ ，
$$
x-\lfloor\frac{x}{n}\rfloor\times n=\frac{xk-\lfloor\frac{xk}{kn}\rfloor\times kn}{k}
$$
同余：
若整数 $a,b$ 除以正整数 $m$ 的余数相等，则称 $a,b$ 模 $m$ 同余，记为 $a\equiv b (\bmod m)$
逆元：
设 $a$ 为整数，$n$ 为正整数，若整数 $b$ 满足，$ab\equiv 1(\bmod n)$，则称 $b$ 为 $a$ 模 $n$ 的逆元。
- 当且仅当 $\gcd(a,n)=1$ 时， $a$ 模 $n$ 的逆元存在。
- 如果 $b_1,b_2$ 为 $a$ 模 $n$ 的逆元，则必有 $b_1\equiv b_2(\bmod n)$ ，即 $a$ 模 $n$ 的逆元在模 $n$ 意义下唯一。
由于 $a$ 的逆元唯一，可记为 $a^{-1}$ 或 $\frac{1}{n}$ 。可以定义 $\frac{1}{a}\bmod n$为 $a$ 模 $n$ 的逆元中绝对值最小的数，并取与 $a$ 相同的符号。
费马小定理：
对于质数 $p$ 和任意整数 $a$ ，若 ${\rm gcd}(a,p)=1$ ，则 $a^p\equiv a (\bmod p)$
设有数列 $S={1,2,3,\cdots,p-1}，S\bmod p=S$
则 $S \times a = a,2a,3a,\cdots,(p-1)a$
$\therefore (S\times a\bmod p=(S\bmod p\times\ a\bmod p)\bmod p$ $({\rm gcd}(a,p)=1)$
$\therefore$ 上式$=S\times (a\bmod p)$ 而 ${\rm gcd}(p,a\bmod p)=1$
$\therefore \prod_{i=1}^{p-1}i\equiv \prod_{i=1}^{p-1}a\times i\ (\bmod p)$
$\therefore (p-1)!\equiv a^{p-1}\times (p-1)!(\bmod p)$
$\therefore 1\equiv a^{p-1}(\bmod p)$
$\therefore a\equiv a^p(\bmod p)$
求逆元：
若 $p$ 为质数，且 $\gcd(a,p)=1$ ,则 $a^{-1}\equiv a^{p-2}(\bmod p)$ 。 计算时间复杂度 $O(\log p)$ 。
$a^{p-1}\equiv 1(\bmod p)$
$\therefore a\times a^{p-2}\equiv 1(\bmod p)$
$\therefore a^{-1}\equiv a^{p-2}(\bmod p)$
线性求逆元：
inv[1] = 1;
for(int i=2; i<=n; ++i)
inv[i] = ((-1LL*(p/i) % p ) * inv[p%i] % p + p ) % p;
$ \because p\bmod i=p-\lfloor\frac{p}{i}\rfloor\times i$
$\therefore p=\lfloor\frac{p}{i}\rfloor\times i+(p\bmod i)$
$\therefore 0\equiv\lfloor\frac{p}{i}\rfloor\times i+(p\bmod i)(\bmod p)$
$\therefore -(p\bmod i)\equiv\frac{p}{i}\times i(\bmod p)$
$\therefore -\frac{\lfloor \frac{p}{i}\rfloor\times i}{p\ \bmod\ i}\equiv 1(\bmod p)$
$\therefore \frac{1}{i}\equiv-\frac{\lfloor \frac{p}{i}\rfloor}{p\ \bmod\ i}$
欧拉定理：
若正整数 $a,n$ 互质，则 $a^{\varphi(p)}\equiv1(\bmod p)$
推论（扩展欧拉定理）：
$$
a^b\equiv\begin{cases}
a^{b\ \bmod\ \varphi(p)}\ \ \ \ \ \ \ \ \ \gcd(a,p)=1\
a^b\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \gcd(a,p)!=1,b<\varphi(p)\ \ \ \ \ (\bmod p)\
a^{b\ \bmod\ \varphi(p)+\varphi(p)}\ \gcd(a,p)!=1,b\geq\varphi(p)
\end{cases}
$$
证明： $a^b\equiv a^{b\ \bmod\ \varphi(p)}\ \ \gcd(a,p)=1$
$$
设 b=q\times \varphi(p)+r\
a^b\equiv a^{q\times\varphi(p)+r}\equiv (a{\varphi(p)})q\times a^r\equiv 1^q\times a^r\equiv a^r\equiv a^{b\ \bmod\ \varphi(p)}
$$
例： 求 $a^b\bmod m$ ？
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 2e7+10;
int a, m;
char b[maxn];
int phi(int x) {
int res = x;
int cnt = sqrt(x);
for(int i=2; i<=cnt; ++i) {
if(x % i == 0) {
res = res / i * (i-1);
while(x % i == 0) x /= i;
}
}
if(x > 1) res = res / x * (x-1);
return res;
}
LL quick_pow(LL x, LL y) {
LL res = 1;
while(y) {
if(y&1)
res = (res*x)% m;
x = (x*x) % m;
y >>= 1;
}
return res % m;
}
int main () {
scanf("%d%d%s", &a, &m, b);
int Phi = phi(m); // m 的欧拉函数值
int rmd = 0;
int len = strlen(b);
int flag = 1;
for(int i=0; i<len; ++i) { // 将 b 对 Phi 取模
rmd = rmd * 10;
if(rmd >= Phi) flag = 0;
rmd = rmd % Phi;
rmd = rmd + (b[i]-'0');
if(rmd >= Phi) flag = 0;
rmd = rmd % Phi;
}
if(flag) // 当 b < Phi
printf("%lld\n", quick_pow(a, rmd));
else printf("%lld\n", quick_pow(a, rmd+Phi));
return 0;
}
exgcd:
$Bézout$： 对于任意整数 $a,b$ 存在一堆整数 $x,y$ 满足 $ax+by=\gcd(a,b)$ 。
在 $\gcd$ 最后当 $b=0$ 时，显然 $x=1,y=0$ 满足 $a\times1+0\times 0=\gcd(a,0)$ 。
若 $b>0$ ，则 $\gcd(a,b)=\gcd(b,a\ {\rm mod}\ b)$ 假设有 $x,y$ 满足 $bx+(a\bmod b)y=\gcd(b,a\bmod b)$
$bx+(a\bmod b)y=bx+(a-b\lfloor\frac{a}{b}\rfloor)y=ay+b(x-\lfloor\frac{a}{b}\rfloor y)$
$\therefore x'=y,y'=x-\lfloor\frac{a}{b}\rfloor y$ 可得 $ax'+by'=\gcd(a,b)$ 成立。
$\therefore $ 其通解可表示为 $x=x_0+kb,y=y_0-ka$ 。
模板：
int exgcd(int a, int b, int &x, int &y) {
if(b == 0) {
x = 1;
y = 0;
return a;
}
int d = exgcd(b, a%b, x, y);
int z = x;
x = y;
y = z - (a/b)*y;
return d; // 返回值是 gcd(a, b);
}
对于一般的方程 $ax+by=c$ ，当且仅当 $d\mid c\ (d=\gcd(a,b)\ )$ 时有解。
可以先求出 $ax+by=d$ 的解 $x_0,y_0$ 易得 $ax+by=c$ 的解为 $(c/d)x_0,(c/d)y_0$ 。
$\therefore $ 其通解可表示为 $x=\frac{c}{d}x_0+k\frac{b}{d},y=\frac{c}{d}y_0-k\frac{a}{d}$
求逆元： 即 $ax\equiv 1(\bmod p)$ 求 $x$
$\because ax\equiv 1(\bmod p),\gcd(a,p)=1$
$\therefore ax=1+py$
$\therefore ax+p(-y)=1$
使用 $exgcd$ 求得 $x$ 即可。
中国剩余定理：
设 $m_1,m_2,\cdots,m_n$ 是两两互质的整数， $M=\prod_{i=1}^nm_i,M_i=M/m_i,t_i$ 是线性同余方程 $M_it_i\equiv 1(\bmod m_i)$ 的解，对于任意 $n$ 个整数 $a_1,a_2,\cdots,a_n$ 方程组
$$
\begin{cases}
x\equiv a_1\ (\bmod p)\
x\equiv a_2\ (\bmod p)\
\vdots\
x\equiv a_n\ (\bmod p)
\end{cases}
$$
的解为 $x=\sum_{i=1}^na_iM_it_i$
$\because M_i=M/m_i$
$\therefore M_i$ 是除 $m_i$ 之外所有模数的倍数
$\therefore \forall k!=i,a_iM_it_i\equiv0\ (\bmod m_k)$
$\because a_iM_it_i\equiv a_i\ (\bmod m_i)$
$\therefore x=\sum_{i=1}^na_iM_it_i$ 可使其成立
模板：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 12;
typedef long long LL;
LL a[maxn], m[maxn];
void exgcd(LL a1, LL b, LL& x, LL& y)
{
if(b){
exgcd(b, a1%b, y, x);
y -= (a1/b)*x;
return ;
}
x = 1;
y = 0;
return ;
}
LL CRT(LL a[], LL m[], int n)
{
LL M=1, ans=0, Mi, x, y;
for(int i=1; i<=n; ++i)
M *= m[i];
for(int i=1; i<=n; ++i)
{
Mi = M/m[i];
exgcd(Mi, m[i], x, y); // 求出 Mi 在 模 mi意义下的乘法逆元
x = (x%m[i] + m[i]) % m[i];
ans = (ans + a[i]*x*Mi) % M;
}
return (ans+M) % M; // 求出最小非负整数解
}
int main()
{
int n;
scanf("%d", &n);
for(int i=1; i<=n; ++i)
scanf("%lld%lld", &m[i], &a[i]); // mi是模数， ai是是在模 mi 意义下的同余数
LL ans = CRT(a, m, n);
printf("%lld\n", ans);
}
扩展中国剩余定理：
与中国剩余定理同样，但 $m_1,m_2,\cdots,m_n$ 不互质。
若 $n=2$ ：
$$
\begin{cases}
x\equiv a_1(\bmod m_1)\
x\equiv a_2(\bmod m_2)
\end{cases}
\Rightarrow
\begin{cases}
x= k_1m_1+a_1\
x= k_2m_2+a_2
\end{cases}
(k\in \mathbb{N})
$$
$\therefore m_1k_1+a_1=m_2k_2+a_2\ \ \Rightarrow \ \ m_1k_1-m_2k_2=a_2-a_1$当且仅当 $\gcd(m_1,m_2)\mid a_2-a_1$ 时有解，用 $exgcd$ 求得一组解 $(k_1',k_2')$ ，带入方程组中得 $x=x_0$ 。
$\therefore $ $x$ 的通解为 $x=x_0+z\times {\rm lcm}(m_1,m_2)$
令 $M={\rm lcm}(m_1,m_2),A=x_0$ ，则 $x=A+z\times M\Rightarrow x\equiv A(\bmod M)$
这样就把两个同余式换成了一个同余式，以此类推即可求解。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
LL r[maxn], m[maxn];
LL exgcd(LL a, LL b, LL& x, LL& y)
{
if(b){
LL d = exgcd(b, a%b, y, x);
y -= a/b*x;
return d;
}
x = 1; y = 0;
return a;
}
LL quick_mul(LL a, LL b, LL mod)
{
LL ans = 0;
while(b>0){
if(b&1)
ans = (ans + a) % mod;
a = (a << 1) % mod;
b >>= 1;
}
return ans;
}
LL excrt(int n)
{
LL M=m[1], R=r[1], k1, k2;
for(int i=2; i<=n; ++i)
{
LL a=M, b=m[i];
LL c = ((r[i]-R)%b + b) % b;// 求ax+by=c即求ax同余c(mod b)，所以mod b对于答案没有影响
LL d = exgcd(a, b, k1, k2);
if(c%d != 0) return -1; // 无解
k1 = quick_mul(k1, c/d, b/d); // 找出方程 ak1+bk2=c的最小非负整数解
R += k1 * M;
M = a/d*b;
R = (R%M + M) % M;
}
return (R%M + M) % M;
}
int main()
{
int n;
scanf("%d", &n);
for(int i=1; i<=n; ++i)
scanf("%lld%lld", &m[i], &r[i]); // m[i] 表示模数， r[i] 表示余数
printf("%lld\n", excrt(n));
return 0;
}