本博客源自我的洛谷博客 https://www.luogu.com.cn/article/2xq9k7z8 和 https://www.luogu.com.cn/article/n2wot8r1 （现在改成专栏了），写作时间 2021-08-18 00:40/2021-09-26 20:53

对于本篇文章，看这个就够了： https://oi-wiki.org/math/number-theory/inverse/

$a\cdot a^{-1}\equiv1\pmod b$，$a^{-1}$ 是 $a$ 在模 $b$ 意义下的逆元。

感觉本算法的应用比较广一些。

求法：

线性求从 1 开始连续 n 个数的逆元

先上结论：

$$ i^{-1}\equiv \begin{cases} \text{undifined},&i=0 \\ 1,&i=1 \\ -\left\lfloor\dfrac p i \right\rfloor\cdot(p\bmod i)^{-1},&\text{otherwise}\end{cases} $$

证明：

$\because 1\cdot1=1\equiv1\pmod p\qquad\qquad\qquad\therefore 1^{-1}\equiv1\pmod p$

$\because\left\lfloor\dfrac p i \right\rfloor\cdot i\,+\,(p\bmod i)\equiv0\pmod p\quad\therefore\left\lfloor\dfrac p i \right\rfloor\cdot(p\bmod i)^{-1}\,+\,i^{-1}\equiv0\pmod p$

代码

1
2
3
4

void getInv(int n,int p){//get inv[1~n] (mod p)
	inv[1]=1;for(int i=2;i<=n;i++)
		inv[i]=(ll(p-p/i)*inv[p%i])%p;
}

线性求任意 n 个数的逆元

先通过一次扫描扫出 n 个数前缀乘积数组 $S$

然后通过扩展欧几里得法或快速幂法求出 $S_n^{-1}$

然后从后往前递推求出前缀逆元乘积数组 $S^{-1}$

依靠 $a_i^{-1}=\dfrac{S_i^{-1}}{S_{i-1}}$ 求出 $a^{-1}$

代码

1
2
3
4
5
6
7

int s[5000005],r[5000005];	//r->s^{-1}
int* getInv(int* __first,int* __last,int p){
	s[0]=1;for(int i=1;i<=(__last-__first);++i)s[i]=(ll(s[i-1])**(__first+i-1))%p;
	int y;exgcd(s[__last-__first],p,r[__last-__first],y);r[__last-__first]=(r[__last-__first]%p+p)%p;
	for(int i=__last-__first;i>=1;i--)r[i-1]=(ll(r[i])**(__first+i-1))%p;
	for(int i=1;i<=__last-__first;i++)inv[i]=(ll(s[i-1])*r[i])%p;return inv+1;
}

欧拉函数

欧拉函数表示小于等于 $n$ 的正整数中与 $n$ 互质的数的个数，记作 $\varphi(n)$

举个例子：小于等于 10 的正整数有 {1,2,3,4,5,6,7,8,9,10}，其中有且只有 {1,3,7,9} 与 10 互质，故 $\varphi(10)=4$

OEIS 上的欧拉函数序列 ：

欧拉函数的性质

• 积性函数

$\text{if } \gcd(a,b)=1 \implies\varphi(a)\times\varphi(b)=\varphi(a\times b)$

（特别的，$n\in\text{odd}\implies\varphi(2n)=\varphi(n)$）

• $n=\sum_{d|n}\varphi(d)$

（特别的，$n\in\text{prime}\iff\varphi(n)=n-1$）

• 把 $n$ 分解质因数：$n=\prod_{i=1}^s p_i\;(p_i\in\text{prime})\implies\varphi(n)=n\times\prod_{i=1}^s \dfrac{p_i-1}{p_i}$

• 欧拉定理

$\gcd(a,m)=1\implies a^{\varphi(m)}\equiv1\pmod m$

例： $5^{\varphi(6)}=5^2=25\equiv1\pmod6$

$\qquad\,7^{\varphi(12)}=7^4=2401\equiv1\pmod{12}$

…

• 扩展欧拉定理

$$ a^b=\begin{cases}a^{b\bmod\varphi(b)},&\gcd(a,p)=1 \\ a^b,&\gcd(a,p)\ne1,b<\varphi(p) \\ a^{(b\bmod\varphi(p))+\varphi(p)},&\gcd(a,p)\ne1,b\ge\varphi(p)\end{cases}\quad\pmod p$$

求 $\varphi(n)$

挖坑

莫比乌斯函数

$$\mu(n)=\begin{cases}1,&n=1\\0,&n=k\cdot z^2;(k,z\in\mathbb Z)\\(-1)^k,&n=\prod_{i=1}^kp_i,;p_i\in\text{prime}\end{cases}$$

举个例子：$10=2\times5$ ，故 $\mu(10)=(-1)^2=1$

$\qquad\qquad\;\;24=2^3\times3$，故 $24=6\times2^2$，$\mu(24)=0$

莫比乌斯函数的性质

• 积性函数

$\text{if } \gcd(a,b)=1 \implies\mu(a)\times\mu(b)=\mu(a\times b)$

$$\sum\limits_{d|n}\mu(d)\;=\begin{cases}1,&n=1\\0,&n\ne1\end{cases}$$

求 $\mu(n)$

挖坑