逆元
\(a \div b \mod p = a \times \dfrac{1}{b} \mod p\)
费马小定理: \(a^{p-1} \mod p = 1\)，也就是 \(a^{p-1} \equiv 1 \pmod p\)。
得 $a^{p-2} \equiv \dfrac{1}{a} \pmod p $。
所以可以直接带逆元为 \(a^{p-2} \mod p\)。
\(\varphi(i)\) 指 \(1\) 到 \(i\) 中有多少数与 \(i\) 互质。
\(a^{\varphi(p)} \equiv 1 \pmod p\)
相似的 可以得 \(a^{\varphi(p)-1} \equiv \dfrac{1}{a} \pmod p\)。
所以可以直接带逆元为 \(a^{\varphi(p)-1} \mod p\)。
显然对于质数 \(p_1\)，有 \(\varphi(p)=p-1\)，还有 $\varphi(p^2) = p_1^2 - p_1 $ 和 \(\varphi(p^k) = p_1^k - p_1^{k-1}\)。
还得\(\varphi(p_1^{k_1} \times p_2^{k_2})=p_1^{k_1} \times p_2^{k_2} - p_1^{k_1-1} \times p_2^{k_2} - p_1^{k_1} \times p_2^{k_2-1}+ p_1^{k_1-1} \times p_2^{k_2-1})\)
设\(p_1^{k_1} \times p_2^{k_2} = n\) 显然有
\(\varphi(n)=n-\dfrac{n}{p_1}-\dfrac{n}{p_2}+\dfrac{n}{p_1 \times p_2}=n \times (1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2})\)。
所以，我们得到结论 ，设 \(p\) 为 \(n\) 的分解质因数，得\(\varphi(n)=n \times (1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2}) \cdots n \times (1-\dfrac{1}{p_k})\)
代码实现：
因为c++不支持分数计算，但是，显然 \(1-\dfrac{1}{x}=\dfrac{x-1}{x}\)，所以，可以写成\(\varphi(n)=n \times (p_1-1) \div p_1 \times (p_2-1) \div p_2 \cdots \times (p_k-1) \div p_k)\)，为了计算，一般写成先除后加的形式。
代码:
int get_phi(int n){
int phi=n;
for(int i=2;i*i<=n;i++){
if(n%i==0){
phi=phi/i*(i-1);
while(n%i==0)n=n/i;
}
}
if(n!=1)phi=phi/n*(n-1);
return phi;
}
int fastpow(int x,int y,int p){
if (y==0) return 1;
int z=fastpow(x,y/2,p);
z=1ll*z*z%p;
if(y%2==1) z=1ll*z*x%p;
return z;
}
int a,b;
int ans=fastpow(a,get_phi(b)-1,b);
exgcd
解方程 \(ax+by=\gcd(a,b)\)。
最后一层的方程是好解的 ，显然有 \(x=1,y=0\)，现在考虑通过一层去推另一层，现在已知 \(x' b + y'(a \mod b)=\gcd(a,b)\)，根据取模的定义得$ x'\times b + y'(a - b \times \lfloor \dfrac{a}{b} \rfloor)=\gcd(a,b)$，拆开可得 \(y'\times a+x'\times b - y' \times (b \times \lfloor \dfrac{a}{b} \rfloor)=\gcd(a,b)\)，则可得 \(x=y'\)，\(y=x'-y'\times (\lfloor \dfrac{a}{b} \rfloor)\)。
代码:
int exgcd(int a,int b,int &x,int &y){
if(b==0){
x=1;
y=0;
return a;
}
int xp,yp;
int g=exgcd(b,a%b,xp,yp);
x=yp;
y=xp-yp*(a/b);
return g;
}
CRT/ExCRT （中国剩余定理/拓展中国剩余定理）
解方程组
\[\left\{ \begin{array}{lc} x \mod p_1=b_1\\ x \mod p_2 = b_2\\ \cdots \\ x \mod p_n = b_n \\ \end{array} \right. \]考虑合并方程，这样，\(n-1\) 轮之后，可以合并成一个方程。
这里提供一个暴力方法，显然 \(P = \text{lcm}(p_1,p_2)\)，但是，如何求 \(X\)？显然不能一个一个枚举，太慢。
我们把 \(X\) 设为 \(b_1\)，然后持续 \(+ p_1\)，直到 \(X \mod p_2 = 0\) 为止。
但是我们需要判断是否有解，因为无解会死循环，如果 \(X > P\)，显然无解。
注意优化，如果\(a_1<a_2\)，那么，交换 \(a_1\) 和 \(a_2\)，单次操作\(O(\min(a1,a2))\)，而且方程越多，跑的越快。这种暴力方法被称作大数翻倍法。
给出合并代码:
int merge(int a1,int b1,int a2,int b2,int &a,int &b){
if(a1<a2)swap(a1,a2),swap(b1,b2);
a=a1/gcd(a1,a2)*a2;
b=b1;
while(b%a2!=b2&&b<=a)b+=a1;
if(b%a1==b1&&b%a2==b2)return 1;
else return 0;
}
质数筛法
比较简单，给两种及其简单的质数筛法（没讲欧拉筛 qwq）：
void s1(int n){//O(nlogn)
for(int i=2;i<=n;i++){
for(int j=2*i;j<=n;j++)not_prim[j]=1;
}
}
void s2(int n){//O(nloglogn)
for(int i=2;i<=n;i++){
if(not_prim[i]==0){
for(int j=2*i;j<=n;j++)not_prim[j]=1;
}
}
}
线性求逆元
方法一
令\(fac_i=i!\)，令\(ifac_i=i!\)的逆元 ，先求出\(ifac_n\)，再倒推\(ifac_i=ifac_{i-1} \times n\)。
则：\(inv_i=fac_{i-1} \times ifac_i\)。
代码，咕咕。
方法二
先咕咕。
标签：ifac,int,dfrac,varphi,times,无题,mod From： https://www.cnblogs.com/ScapeGoatTree/p/17996883