基础数论
前置芝士：
等比数列求和: \(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_1^2+...+p_1^{c_1})\times\cdots\times (1+p_m+p_m^2+...+p_m^{c_m})=\prod_{i=1}^m\sum_{j=0}^{c_i}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(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)=p^k-p^{k-1}=(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^{c_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) \]
设 \(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 p^m}\varphi(d)=\sum_{i=0}^m\varphi(p^i)=1+\sum_{i=0}^{m-1}(p-1)\times p^i(p为质数)\)
\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ =1+(p-1)\times (1+p+\cdots+p^{m-1})\)
\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ =1+(p-1)\times \frac{1-p^m}{1-p}=p^m\)\(\therefore f(p^m)=p^m\)
\(\therefore f(n)=f(\prod_{i=1}^np_i^{c_i})=\prod_{i=1}^nf(p_i^{c_i})=\prod_{i=1}^np_i^{c_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,n\) 互质，则满足 \(a^x\equiv 1(\bmod n)\) 的最小正整数 \(x_0\) 是 \(\varphi(n)\) 的约数。
假设满足 \(a^x\equiv 1(\bmod n)\) 的最小正整数 \(x_0\) 不是 \(\varphi(n)\) 的约数。
设 \(\varphi(n)=qx_0+r(0<r<x_0)\)
\(\therefore a^{x_0}\equiv 1(\bmod n)\)
\(\therefore a^{qx_0}\equiv 1(\bmod n)\)
\(\because a^{\varphi(n)}\equiv 1(\bmod n)\)
\(\therefore a^r\equiv 1(\bmod n)\)
而 \(r<x_0\) ，这与 \(x_0\) 最小矛盾，所以假设不成立。
例： 求 \(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;
}