本博客源自我的洛谷博客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

代码

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}

代码

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}

\qquad\,.\,.\,.\;.\,.\,.

• 扩展欧拉定理

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)

挖坑