持续更新，主要是在自己忘了时能来这看看
费马小定理
若 \(p\) 为素数且 \(gcd(a,p)=1\)，则 \(a^{p-1}\equiv 1(\text{mod}\; p)\)
欧拉定理
若 \(gcd(a,m)=1\),则\(a^{\phi(m)} \equiv 1 \; ( \text{mod} \;m)\)
扩展欧拉定理
若 \(b \ge \phi(p)\)有
\[a^b \equiv a^{b\;\text{mod} \;\phi(p)+\phi(p)} \; ( \text{mod} \;p) \]扩展欧几里得
https://www.cnblogs.com/blue-tsg/p/16828622.html
Lucas定理
用于求解 \(n,m\) 很大但是 \(p\) 很小的时候
\[C(n,m)\equiv C(n/p,m/p)\times C(n\; \text{mod}\; p,m\; \text{mod}\; p)\;(\text{mod}\; p) \]线性求逆元
\[inv_i=(-\frac{p}{i})\times inv_{p\;\text{mod} \;i} \]中国剩余定理(crt)
\[ \begin{cases} x\equiv a_1\pmod {n_1}\\ x\equiv a_2\pmod {n_2}\\ \vdots\\ x\equiv a_k\pmod {n_k}\\ \end{cases} \]其中 \(n_i\) 两两互质，求解最小正整数解 \(x\)
记\(n=\prod_{i=1}^{n}n_i,m_i=\frac{n}{n_i},m_i^{-1}\)为 \(m_i\) 关于 \(n_i\) 的逆元
\[x=\sum_{i=1}^{k}a_i\times m_i\times m_i^{-1} \]证明：
因为 对于任意 \(j\;(i\neq j)\),有 \(m_j\equiv 0\;\pmod {n_i}\) 所以有：
扩展中国剩余定理
当 \(n_i\) 不互质时，考虑两两合并方程
对于:
\[\begin{cases} a\equiv r_1 \pmod {m_1} \\ a\equiv r_2 \pmod {m_2} \end{cases} \]有：
\[a=k_1m_1+r_1=k_2m_2+r_2 \]即：
\[k_1m_1-k_2m_2=r_2-r_1 \]用 \(\text{exgcd}\) 求解此不定方程和判断无解
对与求出的特解 \(x'\)，通解 \(x=x'+k\times \text{lcm}(m_1,m_2)\)
所以两方程可以合并为 \(a\equiv x' \pmod {\text{lcm}(m_1,m_2)}\)
代码
ll r1,m1,r2,m2,n;
ll exgcd(ll a,ll b,ll &x,ll &y){
if(!b){
x=1;y=0;return a;
}
ll g=exgcd(b,a%b,y,x);
y-=(a/b)*x;
return g;
}
ll lcm(ll a,ll b){
ll x,y;
ll g=exgcd(a,b,x,y);
return a/g*b;
}
ll solve(ll a,ll b,ll c){
ll x,y;
ll g=exgcd(a,b,x,y);
if(c%g) return -1;
b/=g;c/=g;
return (x*c%b+b)%b;
}
void merge(){
ll x=solve(m1,m2,r2-r1);
if(x==-1){puts("-1");exit(0);}
r1=x*m1+r1;
m1=lcm(m1,m2);
r1=(r1%m1+m1)%m1;
}
signed main(){
n=read();
for(int i=1;i<=n;i++){
if(i==1) m1=read(),r1=read();
else m2=read(),r2=read(),merge();
}
printf("%lld\n",(long long)r1);
return 0;
}
第二类斯特林数·行
定义：把 \(n\) 个不同的小球放进 \(m\) 个相同的盒子里的方案数，记作\(\begin{Bmatrix} n\\m\end{Bmatrix}\) 或 \(S(n,m)\)
递推式：
\[S(n,m)=S(n-1,m-1)+m \times S(n-1,m) \]相当于讨论第 \(n\) 个球放哪，若放入一个新盒子，所有新盒子等价，方案数为 \(S(n-1,m-1)\)，若放入已经有球的盒子，因为小球不一样，放入不同的盒子方案是不一样的，所以乘个 \(m\)
容斥原理：
\[S(n,m)=\frac{1}{m!}\sum_{k=0}^{m}(-1)^k\times C(m,k) \times (m-k)^n \]相当于枚举空盒个数 \(k\),剩下的随便放，最后要求 \(k=0\) 时的值，但是有重复（随便放也可能产生空盒），所以容斥一下
把组合数拆开再化简一下
\[\begin{aligned} S(n,m)&=\frac{1}{m!}\sum_{k=0}^{m}(-1)^k\times \frac{m!}{k!(m-k)!} \times (m-k)^n \\ &=\sum_{k=0}^{m}\frac{(-1)^k}{k!}\times \frac{(m-k)^n}{(m-k)!} \end{aligned} \]这是个卷积形式，直接一个NTT可以在 \(n\log n\)复杂度内求解
\(S(n,0),S(n,1) \ldots S(n,n)\)
一些性质：
- \(n^k=\sum_{i=0}^{k}S(k,i)\times i! \times C(n,i)\)
Min_Max 容斥
记 \(max(S)\) 为集合 \(S\) 中的最大值，\(min(S)\) 为集合 \(S\) 中的最小值，\(∣S∣\) 为集合 \(S\) 的元素数量，那么以下两个等式成立
\[max(S)=\sum_{T\subseteq S}(-1)^{|T|+1}min(T) \\ min(S)=\sum_{T\subseteq S}(-1)^{|T|+1}max(T) \]性质：
1.在期望下成立，即：
\[E(max(S))=\sum_{T\subseteq S}(-1)^{|T|+1}E(min(T)) \\ E(min(S))=\sum_{T\subseteq S}(-1)^{|T|+1}E(max(T)) \] 标签：pmod,text,ll,笔记,times,学习,数学,sum,equiv From： https://www.cnblogs.com/blue-tsg/p/17034092.html