前言
前置知识（这个应该很显然）：\(\operatorname{lcm}(a,b)=\dfrac{ab}{\gcd(a,b)}\)
线性筛素数
直接上代码。
const int MAXN=100000008;
bool np[MAXN];
vector<int> prm,pre;
void gg(const int N=100000000){
pre.resize(N+1);
for(int i=2;i<=N;i++){
if(np[i]==false){
prm.push_back(i);
pre[i]=i;
}
for(auto j:prm) if(i*j<=N){
int k=i*j;
pre[k]=j;
np[k]=true;
if(i%j==0) break;
}else break;
}
}
说明一下，prm 存了所有范围内的素数，pre 存了第 \(i\) 个数的最小质因子。
这个板子直接背过就好了。（其实是我懒得讲）
不等式方程（exgcd）
形如 \(ax+by=c\) 的方程（\(a,b\) 为整数），方程有解当且仅当 \(\gcd(a,b) \mid c\)
欧几里得算法：\(\gcd(a,b)=\gcd(b,a \bmod b)\)。
\(ax+by=\gcd(a,b)\) 求解：
当 \(a|b\) 时，\(ax+by=\gcd(a,b)\) 解为 \(\begin{cases}x=0\\y=1\end{cases}\)
\(\begin{aligned}\because ax+by&=\gcd(a,b)\\&=\gcd(b,a \bmod b)\\&=bx_1+(a\bmod b)y_1\\&=bx_1+(a-\lfloor\dfrac{a}{b}\rfloor \times b)y_1\\&=bx_1+(a-\lfloor\frac{a}{b}\rfloor \times b)y_1\\&=ay_1+b(x_1-\lfloor\frac{a}{b}\rfloor \times y_1) \end{aligned}\)
\(\therefore \begin{cases}x=y_1\\y=x_1-\lfloor \frac{a}{b} \rfloor \times y_1 \end{cases}\)
\(\therefore\) 可以递归求解。
\(\color{white}{\text{公式对不齐好难受啊。QWQ}}\)
递归函数
void gg(int &x,int &y,int a,int b){
if(a%b==0){
x=0,y=1;
}else{
int xx,yy;
gg(xx,yy,b,a%b);
x=yy;y=xx-a/b*yy;
}
}
裴蜀定理（写于 2023.4.14）
这个是后补的。QWQ
定义
设 \(a,b\) 是不全为零的整数，则存在整数 \(x,y\) , 使得 \(ax+by=\gcd(a,b)\)。
然后就发现前面的式子求的就是裴蜀定理的式子。
然后写一个我自己发现的东西：（只不过我看过的文章都没讲过，可能是因为为太简单了）
求 \(ax+by=c\) 的解，其中 \(a,b\) 为整数且 \(\gcd(a,b)|c\)。
首先求出 \(ax+by=\gcd(a,b)\) 的解，设解为 \(\begin{cases}x=x'\\y=y'\end{cases}\)
再设 \(k=\dfrac{c}{\gcd(a,b)}\)，则 \(ax+by=c\) 的解为 \(\begin{cases}x=kx'\\y=ky'\end{cases}\)
然后就没了。QWQ
进一步的结论可以去下面的链接。
同余
概念
对两个整数 \(a\)，\(b\)，如果它们除以 d 的余数相同，则称它们 模
\(d\) 同余，记作：
一个小知识
\[a-k \times b=r \to a \equiv r \pmod b \]（\(k\) 为任意整数）
欧拉函数
\(\varphi \leftarrow\) 就是这个玩意。
定义
欧拉函数 \(\varphi(n)\) 表示小于等于 \(n\)（其实等不等于 \(n\) 无所谓，因为 \(n\) 一定不与 \(n\) 互质）且与 \(n\) 互质的正整数（与 \(n\) 互质即对于一个数 \(i\)，\(\gcd(i,n)=1\) 或者说是 \(n \perp i\)）的个数。
特别的，\(\varphi(1)=1\)。
顺便提一嘴，\(1\) 与任何数都互质。
显然， 对于一个正整数 \(a\)，\(a\) 是质数当且仅当 \(\varphi(a)=a-1\)。
性质
积性：如果对于任意两个正整数 \(a,b\)，如果 \(\gcd(a,b)=1\)（即 \(a \perp b\)），\(\varphi(a \times b)=\varphi(a)\times\varphi(b)\)。
欧拉反演：\(\sum\limits_{d \mid n}\varphi(d)=n\)。（\(\sum_{d \mid n}F(d)\) 表示把 \(n\) 以内所有能整除 \(n\) 的数 \(d\) 带入 \(F(d)\) 中求和）
性质三（很重要）：对于任意质数 \(p\)，\(\varphi(p^k)=p^k-p^{k-1}\)。
接下来是举例子时间。QWQ
\[\begin{aligned}\varphi(3 \times 7)&=\varphi(21)\\&=12\end{aligned} \]\[\begin{aligned}\varphi(3)\times\varphi(7)&=2\times6\\&=12\end{aligned} \]然鹅，
\[\begin{aligned}\varphi(2 \times 4)&=\varphi(8)\\&=4\end{aligned} \]\[\begin{aligned}\varphi(2)\times\varphi(4)&=1\times2\\&=2\end{aligned} \]\[\begin{aligned}&\because \gcd(2,4)\ne1 \\&\therefore \varphi(2 \times 4) \ne \varphi(2)\times\varphi(4)\end{aligned} \]\[\begin{aligned}\sum\limits_{d \mid 8}\varphi(d)&=\varphi(1)+\varphi(2)+\varphi(4)+\varphi(8)\\&=1+1+2+4\\&=8\end{aligned} \]
性质三证明：小于等于 \(p^k\) 的数有 \(p^k\) 个，其中 \(p,2\times p,3\times p...t\times p\) 与 \(p\) 不互质，显然， \(t=p^{k-1}\)，所以与 \(p\) 不互质的数有 \(p^{k-1}\) 个，那么与 \(p\) 互质的数就有 \(p^k-p^{k-1}\) 个，即 \(\varphi(p^k)=p^k-p^{k-1}\)。
计算欧拉函数
单个欧拉函数：设 \(n\) 的唯一分解式（就是质因数分解）为 \(n=p_1^{k_1} \times p_2^{k_2} \times ... \times p_s^{k_s}\)（显然， \(p_1\) 到 \(p_s\) 均为质数，且 \(p_1^{k_1},p_2^{k_2}...p_s^{k_s}\) 两两互质），则 \(\varphi(n)=\prod\limits_{i=1}^s \varphi(p_i^{k_i})\)，\(\prod\limits_{i=1}^s \varphi(p_i^{k_i})\) 能用性质三求解（其实就是 \(\varphi(n)=\prod\limits_{i=1}^s (p_i^{k_i}-p_i^{k_i-1})\)）。
线性筛欧拉函数
在线性筛素数的同时可以筛出欧拉函数，设 \(p\) 是 \(i\) 的最小质因子，分三种情况讨论：
-
\(i\) 为质数，\(\varphi(i)=i-1\)。
-
\(p\) 是 \(\frac{i}{p}\) 的质因子，\(\varphi(i)=\varphi(\frac{i}{p}) \times p\)。
-
\(p\) 与 \(\frac{i}{p}\) 互质，\(\varphi(i)=\varphi(\frac{i}{p}) \times \varphi(p)\)。
证明：
-
显然 -
设 \(i=p^k \times q\)，其中 \(q\) 不含质因子 \(p\)。则 \(\varphi(i)=\varphi(q) \times \varphi(p^k)=\varphi(q) \times (p^k-p^{k-1})=\varphi(q) \times p(p^{k-1}-p^{k-2})=\varphi(q) \times p \times \varphi(p_{k-1})=\varphi(\frac{i}{p}) \times p\)
-
根据积性可得。
假如 C君 在仪仗队的左前方，坐标为 \((0,0)\)。
首先可以发现，对于一个坐标 \((i,j)\)，C君 能看到这个位置当且仅当 \(\gcd(i,j)=1\)，并且在与 C君 位置相交的对角线左右两边能看到的位置对称。
可以推个柿子。
当 \(n\le 2\) 时：
\[ans=2\sum\limits^{n-1}_ {i=1}\sum\limits^{i-1}_ {j=1} [\gcd(i,j)=1] +3 \]\[ans=2\sum\limits^{n-1}_ {i=1} \varphi(i) +3 \]用线性筛欧拉函数即可，记得当 \(n=1\) 时特判一下。
代码：
#include<bits/stdc++.h>
#define XD 114514
#define MAXN 40010
using namespace std;
int n;
int phi[MAXN];
bool np[MAXN];
vector<int> prm,pre;
long long ans;
void gg(){
pre.resize(n+10);
for(int i=2;i<=n;i++){
if(np[i]==false){
phi[i]=i-1;
pre[i]=i;
prm.push_back(i);
}
for(int j=0;j<prm.size();j++){
if(i*prm[j]<=n){
int k=i*prm[j];
pre[k]=prm[j];
np[k]=true;
if(i%prm[j]==0){
phi[k]=phi[i]*prm[j];
break;
}else{
phi[k]=phi[i]*phi[prm[j]];
}
}else break;
}
}
}
int main(){
cin>>n;
if(n==1) cout<<0;
else{
gg();
for(int i=1;i<=n-1;i++) ans+=phi[i];
cout<<(ans+1)*2+1;
}
return 0;
}
欧拉定理
对任意正整数 \(a,m\)，\(\gcd(a,m)=1\)，一定有：\(a^{\varphi(m)} \equiv 1 \pmod m\)。
逆元
逆元补充 （by 2023.5.11）
定义
对于任意正整数 \(x\) 满足 \(x \times x^{-1} \equiv 1 \pmod p\)，则称 \(x^{-1}\) 为 \(x\) 在模 \(p\) 同余下的逆元（其实就跟普通的 \(x \times x^{-1}=1\) 中的 \(x^{-1}\) 差不多，只不过这里的逆元是在模 \(p\) 同余下，而且在模 \(p\) 同余下，\(x\times x^{-1}=1\)，然后就可以得出 \(x^k \times x^{-1} \equiv x^{k-1} \pmod p\)）
为了方便理解，我就先把下文中所有的字母下面带 \(0\) 的都为这个字母代表的数在模某一个数同余下的逆元。（因为我在听课时老师是用 \(x^{-1}\) 表示 \(x\) 在模 \(p\) 同余下的逆元QWQ）
性质（这些记住就行QWQ）
逆元存在性定理：\(x\) 在模 \(p\) 同余下存在逆元当且仅当 \(\gcd(x,p)=1\)。
推论：当且仅当模数 \(p\) 是质数时，\([1, p − 1]\) 内所有整数都存在模 \(p\) 下的逆元。 \(0\) 没有逆元。
逆元唯一性定理：模 \(p\) 同余下，一个整数 \(x\) 的逆元若存在，则唯一。
定理：在模质数 \(p\) 同余下， \([1, p − 1]\) 内所有整数的逆元互不相同。
定理：一个数的逆元的逆元等于它自身。
计算逆元
先上例题。
根据逆元定义可得这是一道求逆元板子题（显然）。
因为题目说输入数据保证一定有解，根据逆元存在性定理可得 \(\gcd(a,b)=1\)。
开始求逆元喽。
（由于 \(k\) 为任意整数，我们不知道它是正数还是负数，就把前面的正负号省略了）
然后可以发现，这不就是一个不定方程吗。（因为 \(a,b\) 为已知量，只需求 \(x\)）
在前面我们知道 \(\gcd(a,b)=1\)，所以可以用递归求解即可。
最后记得把 \(x\) 取模到 \([1,b-1]\) 的范围即可。QWQ
代码如下。
#include<bits/stdc++.h>
#define XD 114514
#define int long long
using namespace std;
inline void gg(int &x,int &y,int a,int b){
if(a%b==0){
x=0,y=1;
}else{
int xx,yy;
gg(xx,yy,b,a%b);
x=yy;
y=xx-a/b*yy;
}
}
signed main(){
int a,b,x,y;
cin>>a>>b;
gg(x,y,a,b);
cout<<(x%b+b)%b;
return 0;
}
当然也可以像下面这样写。
#include<bits/stdc++.h>
#define XD 114514
#define int long long
using namespace std;
inline void gg(int &x,int &y,int a,int b){
if(a%b==0){
x=0,y=1;
return;
}
gg(y,x,b,a%b);
y-=a/b*x;
}
signed main(){
int a,b,x,y;
cin>>a>>b;
gg(x,y,a,b);
cout<<(x%b+b)%b;
return 0;
}
补充
写于 2023.5.25
由于扩展中国剩余定理中有一些比较难懂的东西，结果发现是前面学的有问题，所以在这里来个补充。
先看一道题。（这是我自己出的QWQ）
解 \(ax \equiv b \pmod p\)
按上面的思路可得 \(ax+pk=b\)
由裴蜀定理可得，如果 \(\gcd(a,p) \nmid b\) 则无解。
设 \(\gcd(a,p)=g\)
用 exgcd 可求 \(au+pv=g\)
\(\therefore a\dfrac{bu}{g}+p\dfrac{bv}{g}=g\dfrac{b}{g}=b\)
即 \(x=\dfrac{bu}{g}\)，\(k=\dfrac{bv}{g}\)
这说明 \(x_0\equiv \dfrac{bu}{g}\pmod p\) 是 \(ax\equiv b \pmod p\) 的解。
设 \(x_1\) 是 \(ax\equiv b \pmod p\) 的其他解。
则 \(ax_1 \equiv ax_0 \pmod p\)
所以 \(p \mid ax_1-ax_0\)
这蕴含 \(\dfrac{p}{g} \mid \dfrac{a(x_1-x_0)}{g}\)
因为 \(\dfrac{p}{g}\)，\(\dfrac{a}{g}\) 没有公约数。
所以 \(\dfrac{p}{g} \mid x_1-x_0\)
即 \(x_1=x_0+k\dfrac{p}{g}\)（\(k \in \mathbb{Z}\)）
而相差 \(p\) 的倍数的解被规定相同，所以恰好有 \(g\) 个不同的解。
即取 \(k=0,1,...,g-1\)。
其实学完扩展中国剩余定理再回来看可以感觉到其实 \(ax+by=c\) 也不一定只有一个解或无解。（只不过在 OI 中我们只需要求差不多最小正整数解即可QWQ）
好像很显然的样子QWQ。
欧拉定理的继续
欧拉定理有一个前提条件就是 \(\gcd(a,m)=1\)，根据逆元存在性定理就可得出这个 \(a\) 在模 \(m\) 同余下一定有逆元。让我们推个式子。QWQ
\[a^{\varphi(m)} \equiv 1 \pmod m \]\[a^{\varphi(m)}\times a^{-1} \equiv a^{-1} \pmod m \]\[a^{\varphi(m)-1} \equiv a^{-1} \pmod m \]然后我们就得到了另一个求逆元的方法。（虽然不是很好用）
但是当 \(m\) 是质数时，\(a^{\varphi(m)} \equiv 1 \pmod m\) 就可以转化成 \(a^{m-1} \equiv 1 \pmod m\) 于是费马小定理出现了。
费马小定理
对任意整数 \(a\) 和质数 \(p\)，\(a^{p-1} \equiv 1 \pmod p\)。
根据式子可以推出：
\[a^{-1} \equiv a^{p-2} \pmod{p} \]然后我们就又双叒叕得到了一个求逆元的方法（用快速幂求一下 \(a^{p-2} \bmod p\) 即可）。
上个题QWQ P2613 【模板】有理数取余
求 \(\frac{a}{b} \bmod 19260817\) 的值。
让我们算一算吧。
\[\frac{a}{b} \bmod 19260817 \]\[a \times b^{-1} \bmod 19260817 \]所以我们只需算出 \(b\) 模 \(19260817\) 同余下的逆元。由于 \(19260817\) 为一个质数，用费马小定理求即可。
而无解的情况就是 \(b\) 是 \(19260817\) 倍数，那么 \(b \bmod 19260817\) 一定等于 \(0\)。
直接上代码。
#include<bits/stdc++.h>
#define XD 114514
#define mod 19260817
using namespace std;
inline long long read(){
char ch=getchar(),h;long long w=0;
while(ch>'9' or ch<'0') h=ch,ch=getchar();
while(ch>='0' and ch<='9') w=(w*10+(ch-'0'))%mod,ch=getchar();
if(h=='-') w=-w;
return w;
}
long long a,b;
inline long long gg(long long x,long long k){
//求 x 在模 mod 同余下的逆元，即求 x^(mod-2)%mod 的值
//这里 k 就表示 mod-2 的值
long long ans=1;
while(k){
if(k&1){
ans*=x;ans%=mod;
}
x*=x;x%=mod;
k>>=1;
}
return ans;
}//快速幂是啥偶就不讲了QWQ
int main(){
a=read(),b=read();
if(b==0) cout<<"Angry!\n";
else cout<<a*gg(b,mod-2)%mod;
return 0;
}
线性求逆元
设 \(inv_i\) 表示 \(i\) 的逆元，有递推式：
\[inv_i \equiv - \lfloor \frac{p}{i} \rfloor \times inv_{p \bmod i} \pmod p \]边界为 \(inv_1 = 1\)。
又要开始推式子了。
再解释一下，我们刚开始设 \(p=i \times k +r\)，其中 \(r \in [1,n)\)，显然，\(k=\lfloor \frac{p}{i} \rfloor\)，\(r=p \bmod i\)，这样应该能看懂了吧。QWQ
下面是代码。
#include<bits/stdc++.h>
#define XD 114514
#define MAXN 3000010
using namespace std;
int n,p,inv[MAXN];
int main(){
ios::sync_with_stdio(false);
cin>>n>>p;
inv[1]=1;
for(int i=2;i<=n;i++){
// inv[i]=(1ll*-(p/i)*inv[p%i]%p+p)%p;
inv[i]=1ll*(p-p/i)*inv[p%i]%p;//这两个算式等价，只不过这个少取模一次
//实测，在P3811中第一个用398ms，第二个用338ms
}
for(int i=1;i<=n;i++) cout<<inv[i]<<'\n';
return 0;
}
说句闲话，我刚开始做这道题时一直 \(\color{black}{TLE}\) 了两个点，最后把换行符 endl 改为 '\n' 就 \(\color{green}{AC}\) 了，这个故事告诉我们，珍爱生命，远离 endl。
首先知道：
\[C^m_n=\frac{n!}{m!(n-m)!} \]显然：
之后就把 \(998244353\) 当做 \(p\) 就行了不然打一个九位数太麻烦了。
然后求 \((m!)^{-1}\)，显然：
所以先线性求一遍逆元，然后预处理出所有阶乘的逆元即可。
上代码。
#include<bits/stdc++.h>
#define XD 114514
using namespace std;
int T,N;
const int p=998244353;
int ans;
int main(){
ios::sync_with_stdio(false);
cin>>T>>N;
vector<int> inv(N+1),a(N+1),b(N+1);
inv[1]=1;//inv_i 表示 i 的逆元
a[1]=1;//a_i 表示 i!的值
b[0]=b[1]=1;//b_i 表示 i! 的逆元的值
for(int i=2;i<=N;i++){
inv[i]=1ll*(p-p/i)*inv[p%i]%p;
a[i]=1ll*a[i-1]*i%p;
b[i]=1ll*b[i-1]*inv[i]%p;
}
while(T--){
int n,m,num=1;
cin>>n>>m;
num=1ll*a[n]*b[m]%p*b[n-m]%p;
ans^=num;
}
cout<<ans;
return 0;
}
威尔逊定理（on 2023.7.11）
定理
若 \(p\) 为素数，那么：
\[(p-1)! \equiv -1 \pmod p \]证明
当 \(p=2\) 时，\((p-1)! \equiv 1 \equiv -1 \pmod p\)
取一个大于 \(2\) 的质数 \(p\)，那么对于任意正整数 \(x\)
（\(1 \le x \le p-1\)），它一定有一个逆元，且这 \(p-1\) 个数的逆元不同。对于这些逆元，逆元是它本身的是 \(1\) 和 \(p-1\)。我们可以把剩下的整数 \(2,3,4,...,p-1\) 分成 \((p-3)/2\) 份，每一份的乘积都模 \(p\) 余 \(1\)，这说明：
再在两边同时乘上 \(1\) 和 \(p-1\)，得：
\((p-1)! \equiv p-1 \equiv -1 \pmod p\)
证毕。
它的逆定理为：
正整数 \(p\) 是质数的充要条件为：
\[(p-1)! \equiv -1 \pmod p \]
威尔逊定理用的很少，不过扩展卢卡斯定理可能要用。
中国剩余定理（CRT）
它是用来解决一个问题的。
问题
给定 \(n\) 个线性同余方程：
\[\begin{cases} x \equiv a_1 \pmod {m_1} \\ x \equiv a_2 \pmod {m_2} \\ ... \\ x \equiv a_n \pmod {m_n} \end{cases} \]其中保证 \(m_1,m_2,...,m_n\) 两两互质。求 \(x\) 的通解。
定理
上面的方程组有解，且按如下方式构造：
记 \(M=\prod\limits^n_{i=1}m_i\) ，\(M_i=\frac{M}{m_i}\)，\(t_i\) 为 \(M_i\) 在模 \(m_i\) 同余下的逆元。
则方程组的唯一通解是：
\[x \equiv \sum\limits^n_{i=1}a_i t_i M_i \pmod M \]
证明
显然：
且，
\[M_it_i \equiv 1 \pmod {m_i} \]（能够保证 \(M_i\) 在模 \(m_i\) 同余下一定有逆元）
\[\therefore a_iM_it_i \equiv a_i \pmod{m_i} \]另外，对于一个 \(j\)（\(j \ne i\)），由于 \(m_i | M_j\)，于是 \(M_j \equiv 0 \pmod{m_i}\)。
\[\therefore a_iM_it_i+m_jM_jt_j \equiv a_i \pmod{m_i} \]\[\therefore a_iM_it_i + \sum\limits^n_{j=1,i\ne j} a_jM_jt_j \equiv a_i \pmod{m_i} \]\[\sum\limits^n_{i=1} a_iM_it_i \equiv a_i \pmod{m_i} \]这就验证了 \(x=\sum\limits^n_{i=1} a_iM_it_i\) 是方程组的一组特解。
运用小学知识（其实就是我懒得证明）可得每两组相邻特解之间相差为 \(M\) 的倍数，于是 \(x+kM\) 也是一个特解，由此，通解唯一性得证。
例题
模板题，直接上代码。
#include<bits/stdc++.h>
#define XD 114514
#define MAXN 20
#define int long long
using namespace std;
int n;
void gg(int &x,int &y,int a,int b){//求逆元
if(a%b==0){
x=0,y=1;
return;
}
gg(y,x,b,a%b);
y-=a/b*x;
}
int a[MAXN],b[MAXN],M[MAXN],m=1,t[MAXN],ans;
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];//x=ai*k+bi -> x mod ai=bi mod ai
m*=a[i];
}
for(int i=1;i<=n;i++){
M[i]=m/a[i];
int x=0,y=0;
gg(x,y,M[i],a[i]);
t[i]=(x%a[i]+a[i])%a[i];
}
for(int i=1;i<=n;i++){
ans+=b[i]*t[i]%m*M[i]%m;
ans%=m;
}
cout<<ans;
return 0;
}
然后套模板即可。
拓展中国剩余定理
等我学完再写。QWQ
终于学完力。QWQ（on 2023.5.23）
求
\[\begin{cases} x \equiv a_1 \pmod {b_1} \\ x \equiv a_2 \pmod {b_2} \\ ... \\ x \equiv a_n \pmod {b_n} \end{cases} \]\(x\) 的通解，但是不保证 \(b_1,b_2,...,b_n\) 两两互质。
首先拿出前两个方程。
\[\begin{cases} x \equiv a_1 \pmod {b_1} \\ x \equiv a_2 \pmod {b_2} \end{cases} \]可变为
\[\begin{cases} x = b_1k_1+a_1 \\ x = b_2k_2+a_2 \end{cases} \]（\(k_1,k_2\) 为任意整数）
所以
\[b_1k_1+a_1=b_2k_2+a_2 \]可变为
\[b_1k_1+b_2k_2=a_2-a_1 \]（这里 \(k_2\) 不是 \(-k_2\) 的解释和在用 exgcd 求逆元中 \(k\) 的解释相同）
设 \(g=\gcd(b_1,b_2)\)
就可以用 exgcd 求出 \(b_1h_1+b_2h_2=g\) 的解。
\(h_1,h_2\) 就是 \(ax+by=\gcd(a,b)\) 中的 \(x,y\)。话说这个不应该看不懂吧QWQ
当然如果题目中不保证一定有解到话判断 \((a_2-a_1)\) 是否能被 \(g\) 整除即可。如果 \(g \nmid (a_2-a_1)\) 则无解。
求出 \(h_1\) 和 \(h_2\) 后可求出 \(k_1=\frac{a_2-a_1}{g}h_1\)。
从而得到一组通解。
\[k_1=k_1+\frac{b_2}{g}t \]\[k_2=k_2-\frac{b_1}{g}t \]（\(t\) 为任意整数）
将 \(k_1\) 带入 \(x = b_1k_1+a_1\) 中。
\[x=b_1k_1+\frac{b_1b_2}{g}t+a_1 \]所以
\[x \equiv b_1k_1+a_1 \pmod {\operatorname{lcm}(b_1,b_2)} \]之后继续合并即可。
#include<bits/stdc++.h>
#define XD 114514
#define MAXN 100010
#define ll long long
#define int __int128
using namespace std;
int n,a[MAXN],b[MAXN];
int gcd(int x,int y){
return y==0?x:gcd(y,x%y);
}
int lcm(int x,int y){
return x/gcd(x,y)*y;
}
void exgcd(ll a,ll b,int &x,int &y){
if(a%b==0){
x=0,y=1;
return;
}
exgcd(b,a%b,y,x);
y-=a/b*x;
}
ll cab_a,cab_b;
int k1,k2,g,nem1,nem2,mod;
void solve(int a,int b){
g=gcd(cab_b,b);
if((a-cab_a)%g!=0) exit(0);//无解
exgcd(cab_b,b,nem1,nem2);
k1=(a-cab_a)/g*nem1;
k1=(k1%(b/g)+(b/g))%(b/g);//将 k1 变成正整数
mod=lcm(cab_b,b);
cab_a=((cab_b*k1+cab_a)%mod+mod)%mod;//将 cab_a 变成正整数
cab_b=mod;
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>b[i]>>a[i];
cab_a=a[1],cab_b=b[1];
for(int i=2;i<=n;i++){
solve(a[i],b[i]);
}
cout<<cab_a%cab_b;
return 0;
}
再来解释一下，其实 \(ax+by=\gcd(a,b)\) 如果有解则解有无数个，它的通解为：
\[\begin{cases} x = x + k\dfrac{b}{\gcd(a,b)} \\ y = y-k\dfrac{a}{\gcd(a,b)} \end{cases} \]（\(k\) 为任意整数）
把新的 \(x,y\) 带入 \(ax+by=\gcd(a,b)\) 是可以发现方程还是成立的。
由于题目中要求的是最小非负整数解，所以在代码中要将变量变为正整数。
容斥原理
关于集合的概念看 这里。
说句闲话，我开始了解集合也是开始于上面的链接。
我们有 \(A,B,C\) 三个集合，求 \(|A \cup B \cup C|\) ，可以列出式子：
\[|A \cup B \cup C|=|A|+|B|+|C|-|A \cap B|-|A \cap C|-|B \cap C|+|A \cap B \cap C| \]如果我们有 \(n\) 个集合 \(P_1,P_2,...,P_n\)，则：
\[|\bigcup\limits_{i=1}^n P_i|=\sum\limits_{S\subseteq[1,2,...,n]}(-1)^{|S|-1}|\bigcap\limits_{s\in S}P _ s|\]二项式定理（写于 2023.4.29）
这个主要说的就是 \(\dbinom{n}{m}\) 这东西。
由于这个可能要写的很多，所以我把它放在一篇单独的博客上。
Lucas定理
定义
对于一个质数 \(p\)，
\[\dbinom{n}{m} \equiv \dbinom{\lfloor \frac{n}{p} \rfloor}{\lfloor \frac{m}{p} \rfloor}\dbinom{n \bmod p}{m \bmod p}\pmod p \]证明我暂时不会，先放个链接QWQ。
但是现在会了。QWQ（by 2023.7.11）
建议别看 OI-wiki 上的证明，反正我没看懂。QWQ
证明
在证明之前，要证明一个式子。
\[(1+x)^p \equiv 1+x^p \pmod p \]（其中 \(p\) 为质数）
证明这个式子
首先知道 \((1+x)^p=\sum\limits_{k=0}^p \dbinom{p}{k}x^k\)。
对于 \(\sum\limits_{k=0}^{p} \dbinom{p}{k}\)，由于知道 \(p\) 为质数，所以这里的 \(\dbinom{p}{k}\) 一定是 \(p\) 的倍数，即 \(\dbinom{p}{k} \equiv 0 \pmod p\)，因为 \(\dbinom{p}{k}=\dfrac{p!}{k!(p-k)!}\)，而想要在 \(\dfrac{p!}{k!(p-k)!}\) 消掉 \(p\) 只能是 \(k=p\) 或 \(p-k=p\)，即 \(k=p\) 或 \(0\) ，而对于其他的，分子中有 \(p\) 这个因数，并且 \(p\) 是质数，所以只有分母有 \(p\) 这个因数才行。
所以我们可以得出：
\[(1+x)^p \equiv 1 +\sum\limits_{k=1}^{p-1}\dbinom{p}{k}x^k+x^p \equiv 1+x^p \mod p \]证毕。
现在开始正式证明卢卡斯定理。
先设 \(n=k_np+r_n\)，\(m=k_mp+r_m\)，所以 \(\lfloor \dfrac{n}{p}\rfloor=k_n\)，\(\lfloor \dfrac{m}{p}\rfloor=k_m\)，\(n \bmod p=r_n\)，\(m \bmod p=r_m\)。
\[\begin{aligned}(1+x)^n&=(1+x)^{k_np+r_n}\\&=(1+x)^{k_np}\times (1+x)^{r_n}\\&=((1+x)^p)^{k_n}\times (1+x)^{r_n}\\&\equiv (1+x^p)^{k_n}\times (1+x)^{r_n} \pmod p\\&\equiv \sum\limits_{i=0}^{k_n}\dbinom{k_n}{i}x^{ip}\times \sum\limits_{i=0}^{r_n}\dbinom{r_n}{i}x^i \pmod p\end{aligned} \]那就有：
\[\sum\limits_{i=0}^n\dbinom{n}{i}x^i\equiv \sum\limits_{i=0}^{k_n}\dbinom{k_n}{i}x^{ip}\times \sum\limits_{i=0}^{r_n}\dbinom{r_n}{i}x^i \pmod p \]对于任意一个整数 \(z\)，必定有一组 \(i,j\) 满足 \(x^z=x^{ip}x^j\)。所以 \(z=ip+j\)，那就是说上面的式子中 \(i\) 取任意一个，右面都有一个新的跟它恒等（应该是在模 \(p\) 意义下）。
当上面的式子左面的 \(i=m\) 时，式子右面则分别 \(i=k_m=\lfloor\dfrac{m}{p}\rfloor\)，\(i=r_m=m \bmod p\)。
则：
\[\begin{aligned}\dbinom{n}{m}x^m &\equiv\dbinom{k_n}{k_m}x^{k_mp}\times \dbinom{r_n}{r_m}x^{r_m}\pmod p \\&\equiv\dbinom{k_n}{k_m}\dbinom{r_n}{r_m}x^{k_mp}x^{r_m}\pmod p \\&\equiv\dbinom{k_n}{k_m}\dbinom{r_n}{r_m}x^{k_mp+r_m}\pmod p \\&\equiv\dbinom{k_n}{k_m}\dbinom{r_n}{r_m}x^m\pmod p \end{aligned} \]两边同乘 \(x^m\) 的逆元，便可得出：
\[\dbinom{n}{m} \equiv \dbinom{k_n}{k_m}\dbinom{r_n}{r_m}\pmod p \]即：
\[\dbinom{n}{m} \equiv \dbinom{\lfloor \frac{n}{p} \rfloor}{\lfloor \frac{m}{p} \rfloor}\dbinom{n \bmod p}{m \bmod p}\pmod p \]证毕。
当 \(p\) 不为质数时，就需要用到 exLucas 定理了。
exLucas 定理之后再学。QWQ
例题
模板题。听君一席话，如听一席话。
直接上代码。
#include<bits/stdc++.h>
#define XD 114514
using namespace std;
int t;
int qpow(int x,int y,int p){//快速幂
int ans=1;
while(y){
if(y&1) ans=1ll*ans*x%p;
x=1ll*x*x%p;
y>>=1;
}
return ans;
}
int C(int n,int m,int p){//组合数
if(n<m) return 0;
int a=1,b=1;
for(int i=1;i<=n;i++) a=1ll*a*i%p;
for(int i=1;i<=m;i++) b=1ll*b*i%p;
for(int i=1;i<=n-m;i++) b=1ll*b*i%p;
return 1ll*a*qpow(b,p-2,p)%p;
}
int Lucas(int n,int m,int p){//Lucas 递推
if(n<p and m<p) return C(n,m,p);
return 1ll*Lucas(n/p,m/p,p)*C(n%p,m%p,p)%p;
}
int main(){
cin>>t;
while(t--){
int n,m,p;
cin>>n>>m>>p;
cout<<Lucas(n+m,m,p)<<'\n';
}
return 0;
}
其他（写于 2023.5.23）
这里是其他的一些数论题的题解（算是吧）。
很有意思的一道题。
首先我看到这道题后思考如何由 \(f(x)\) 转变到 \(f(x+1)\)。（时间复杂度最好为 \(O(1)\)）
\[f(x)=\sum\limits^{i=1}_n x \bmod i \]\[f(x)=\sum\limits^{i=1}_n x-\lfloor\frac{x}{i}\rfloor i \]\[f(x)=nx - \sum\limits^{i=1}_n \lfloor\frac{x}{i}\rfloor i \]那么：
\[f(x+1)=n(x+1) - \sum\limits^{i=1}_n \lfloor\frac{x+1}{i}\rfloor i \]\[f(x+1)=n+nx - \sum\limits^{i=1}_n \lfloor\frac{x+1}{i}\rfloor i \]思考从 \(\sum\limits^{i=1}_n \lfloor\frac{x}{i}\rfloor i\) 到 \(\sum\limits^{i=1}_n \lfloor\frac{x+1}{i}\rfloor i\) 数值的变化。
可以发现，只有 \(i | (x+1)\)，从 \(\lfloor\frac{x}{i}\rfloor\) 到 \(\lfloor\frac{x+1}{i}\rfloor\) 的值会加 \(1\)，那么总共的值会加 \(i\)。
所以总共增加的值为 \(x+1\) 的因数之和。
所以 \(f(x+1)=f(x) + n - a_{x+1}\) （\(a_{x+1}\) 是 \(x+1\) 的因数之和）
而且 \(f(1) = n-1\)。（显然）
#include<bits/stdc++.h>
#define XD 114514
#define MAXN 1000010
using namespace std;
int n,a[MAXN];
long long ans;
void cab(){//预处理
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j+=i){
a[j]+=i;
}
}
}
void solve(){//解决问题
ans=n-1;
cout<<ans<<" ";
for(int i=2;i<=n;i++){
ans=ans+n-a[i];
cout<<ans<<" ";
}
}
int main(){
cin>>n;
cab();
solve();
return 0;
}