取余定义： \(a\%b=a-b\left\lfloor \dfrac{a}{b}\right\rfloor\)
整除
\(a|b\) 表示 \(a\) 能被 \(b\) 整除，即 \(b=a\times k (k\in Z)\) 。
同余
\(a \equiv b \pmod m\) 表示 \(a\mod m=b\mod m\) 。
相当于 \(a-b=m\times k(k \in N)\) 。
裴属定理
内容
若 \(a\) , \(b\) 是整数,且 \(\gcd(a,b)=d\) ，那么对于任意的整数 \(x\) , \(y\) , \(ax+by\) 都一定是 \(d\) 的倍数，特别地，一定存在整数 \(x,y\) ，使 \(ax+by=d\) 成立。
同余方程
\[ax\equiv m\pmod b \]\[ax-m=by \]\[ax+by=m \]欧几里得算法
\(\gcd(a,b)=\gcd(b,a\% b)\)
int gcd(int x,int y)
{
if(!y) return x;
return gcd(y,x%y);
}
扩展欧几里得
可以通过欧几里得求 gcd 的过程求解 \(ax+by=\gcd(a,b)\) 。
设 \(\gcd(a，b)=d\) ，当前的式子为 \(ax+by=d\) ，则下一轮要递归的式子为 \(bx_1+(a\% b)y_1=d\) 。
假设我们已经得出了 \(bx_1+(a\% b)y_1=d\) ，需要求出 \(x,y\) 。
\[bx_1+(a\%b)y_1=d \]由 \(a\%b=a-b\left\lfloor \dfrac{a}{b}\right\rfloor\) 可得
\[bx_1+(a-b\left\lfloor\dfrac{a}{b}\right\rfloor)y_1=d \]整理得
\[ay_1+b(x_1-\left\lfloor\dfrac{a}{b}\right\rfloor y_1)=d \]\[\begin{cases}x=y_1\\y=(x_1-\left\lfloor\dfrac{a}{b}\right\rfloor y_1)\end{cases} \]边界：辗转相除最后 \(b=0\) 返回 \(a\) 。
所以当 \(b=0\) 时，我们令 \(x=1\) 即可（ \(y\) 可以为任意数，因为 \(b=0\) ）。
求出了特解，我们就可以推出通解。
设通解为 \(x_k,y_k\) ，
\[\begin{cases}x_k=x+k\cdot\dfrac{b}{\gcd(a,b)}\\y_k=y-k\cdot\dfrac{a}{\gcd(a,b)}\end{cases} (k\in Z) \]其实可以先求出来 \(x_k\) 在将 \(x_k\) 带入进原式得出 \(y_k\) 。
设一个同余方程为 \(ax+by=k\) ，\(\gcd(a,b)=d\)。
由裴蜀定理可知，\(k\) 一定为 \(d\) 的倍数。
所以可以先求出 \(ax_0+by_0=d\) 的解。再求出 \(ax+by=k\) 解。
\[\begin{cases}x=x_0\cdot\dfrac{k}{\gcd(a,b)}\\y=y_0\cdot\dfrac{k}{\gcd(a,b)}\end{cases} \]int x,y;
int exgcd(int a,int b,int &x,int &y)
{
if(!b) {x=1,y=0;return a;}
int d=exgcd(b,a%b,x,y);
int t=x;
x=y;y=t-a/b*y;
return d;
}
逆元
若 \(ab\equiv1\pmod p\) ，\(a,b\) 互质，则称 \(b\) 为 \(a\) 的逆元（\(b=inv(a)\)。其实就是 \(a\) 在模意义下的倒数。
扩展欧几里得求逆元
设 \(b\) 为 \(a\) 模 \(p\) 意义下的逆元，由逆元定义的可得
\[ab+py=1 \]使用扩展欧几里得即可
int x,y;
void exgcd(int a,int p,int &x,int &y)
{
if(!b) {x=1,y=0;return ;}
exgcd(p,a%p,x,y);
int t=x;
x=y;y=t-a/p*y;
return ;
}
int main(){
a=read(),p=read();
exgcd(a,p,x,y)
printf("%lld",(x%p+p)%p);//（ x 一直加 p 直到大于 0 ）
}
费马小定理求逆元
费马小定理为：如果 \(p\) 是一个质数，而整数 \(a\) 不是 \(p\) 的倍数，则有 \(a^{p-1}\equiv1\pmod p\) 。
由逆元的定义可以得出
\[a\cdot inv(a)\equiv 1\equiv a^{p-1}\pmod p \]\[inv(a)\equiv a^{p-2}\pmod p \]用快速幂计算即可
inline int qpow(int a,int p){
int b=p-2;int base=a,ans=1;
while(b){
if(b&1) ans=(ans*base)%p;
base=(base*base)%p;
b>>=1;
}
return ans;
}
线性递推法
设 \(p=aq+r\) ，则 \(q=\left\lfloor\dfrac{p}{a}\right\rfloor,r=p\%a\) 。
\[aq+r\equiv0\pmod p \]\[a\equiv-r\cdot inv(q)\pmod p \]\[inv(a)\equiv-q\cdot inv(r)\pmod p \]可得递推式：
\[inv(a)=-(\dfrac{p}{a})\cdot inv(p\%a)\pmod p \]int inv[M];
inline void getInv(int n,int p)
{
inv[1]=1;
for(int i = 2;i <= n;i++){
inv[i]=-p/i*inv[p%i];
inv[i]=(inv[i]%p+p)%p;
}
}
中国剩余定理（CRT）
出自《孙子算经》
有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？
本质是求解一个同余方程组
\[\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_i\) 两两互质。
我们可以将方程组分开来看：
\[\begin{cases}x_1\equiv a_1\pmod {m_1}\\x_2\equiv a_2\pmod {m_2}\\...\\x_n\equiv a_n\pmod {m_n}\end{cases} \]只有当 \(m_1|x_2\) 时， \(x_1+x_2 \equiv a_1\pmod {m_1}\)
使 \(x=\sum_{i=1}^n x_i\) ，我们设 \(p=\prod_{i=1}^n m_i, M_i=\dfrac{p}{m_i},r_i=\dfrac{x_i}{M_i}\) ，解下面的同余方程：
\[\begin{cases}M_1\cdot r_1\equiv a_1\pmod {m_1}\\M_2\cdot r_2\equiv a_2\pmod {m_2}\\...\\M_n\cdot r_n\equiv a_n\pmod {m_n}\end{cases} \]因为 \(m_i\) 两两互质，可以用 exgcd 求解，即求关于 \(w_i\) 的同余方程：
\[\begin{cases}M_1\cdot w_1\equiv 1\pmod {m_1}\\M_2\cdot w_2\equiv 1\pmod {m_2}\\...\\M_n\cdot w_n\equiv 1\pmod {m_n}\end{cases} \]（相当于求 \(M_i\) 的在模 \(m_i\) 意义下的逆元 \(inv(M_i)|_{m_i}\) ）
将解代回得 \(r_i=a_i\cdot w_i\)
再将 \(r_i\) 代回得 \(x_i=r_i\cdot M_i=a_i\cdot M_i\cdot w_i=a_i\cdot M_i\cdot inv(M_i)|_{m_i}\)
解即为
\[x\equiv \sum_{i=1}^n a_i\cdot M_i\cdot inv(M_i)|_{m_i} \pmod p \]for(int i = 1;i <= n;i++)
a[i]=read(),b[i]=read(),P*=a[i];
for(int i = 1;i <= n;i++)
{
int M=P/a[i];
ans+=(b[i]*M*inv(M,a[i]))%P;
}