Note - 数论（部分）

Posted on Edited on

欧拉定理和欧拉函数

欧拉函数：

定义式：

φ(x)=∑i=1x[gcd⁡(i,x)=1]\varphi(x) = \sum_{i=1}^{x} [\gcd(i,x)=1]

根据定义可证欧拉函数是积性函数。

  1. 筛法

很容易得出 φ(pk)=pk−pk−1    (p∈P)\varphi(p^k) = p^k-p^{k-1}\ \ \ \ (p\in\mathbb{P}) 。

进而得出 φ(pk)=p⋅φ(pk−1)    (p∈P)\varphi(p^k) = p\cdot\varphi(p^{k-1})\ \ \ \ (p\in\mathbb{P}) 。

那么有当 x=p⋅y(p∈P)x=p\cdot y(p\in\mathbb{P}) 时有

φ(p⋅y)=φ(p)⋅φ(y)=(p−1)⋅φ(y)    (gcd⁡(p,y)=1)\varphi(p\cdot y) = \varphi(p)\cdot \varphi(y) = (p-1)\cdot \varphi(y)\ \ \ \ (\gcd(p,y)=1)

φ(p⋅y)=φ(pk⋅ypk−1)=φ(pk)⋅φ(ypk−1)=p⋅φ(pk−1)⋅φ(ypk−1)=p⋅φ(y)\varphi(p\cdot y) = \varphi(p^k\cdot \frac{y}{p^{k-1}}) = \varphi(p^k)\cdot\varphi(\frac{y}{p^{k-1}}) = p\cdot\varphi(p^{k-1})\cdot\varphi(\frac{y}{p^{k-1}}) = p\cdot \varphi(y)

(gcd⁡(p,y)≠1,gcd⁡(pk,ypk−1)=1)(\gcd(p,y)\neq 1, \gcd(p^k, \frac{y}{p^{k-1}}) = 1)

运用以上两个公式就可以线性筛了。

或者可以变换成各种形式用其他筛法。

  1. 推式子

常用的式子：

φ(x)=∏i=1k(piai−piai−1)=x⋅∏i=1kpi−1pi    (∀pi∈P;∏i=1kpiai=x;i≠j,pi≠pj)\varphi(x) = \prod_{i=1}^k ({p_i}^{a_i}-{p_i}^{a_i-1}) = x\cdot\prod_{i=1}^k \frac{p_i-1}{p_i}\ \ \ \ (\forall p_i\in\mathbb{P}; \prod_{i=1}^k{p_i}^{a_i} = x;i\neq j,p_i\neq p_j)

欧拉定理：

ifgcd⁡(a,p)=1, aφ(p)≡1(mod p)if \gcd(a,p)=1,\ a^{\varphi(p)}\equiv 1(mod\ p)

我有一个伪证：由于 aia^i 与 pp 互质，故在 [0,p−1][0,p-1] 中有 p−φ(p)p-\varphi(p) 个数是不会出现的，其他数构成周期为 φ(p)\varphi(p) 的循环，故 aφ(p)+1≡aa^{\varphi(p)+1}\equiv a 。

当然，这是错的，只能帮助理解。现在懒得学证明了。

欧拉定理可以用来求逆元。但我们更多情况下还是用费马小定理和扩展欧几里得算法求。

逆元：

当 a,pa,p 互质时，存在唯一的 b (mod p)b\ (mod\ p) 使得 a⋅b≡1 (mod p)a\cdot b\equiv 1\ (mod\ p) 。记 bb 为 1a\frac{1}{a} 或 a−1a^{-1} 。

证明还不会。

欧拉定理求逆元： a−1≡aφ(p)−1 (mod p)a^{-1} \equiv a^{\varphi(p)-1}\ (mod\ p) 。

可以用线性筛和快速幂求。

费马小定理：

欧拉定理中，当 p∈Pp\in\mathbb{P} 时， ap−1≡1 (mod p)a^{p-1}\equiv 1\ (mod\ p) 。

费马小定理求逆元十分常用。当题目给的模数是一个很大的质数时经常用费马小定理。

a−1≡ap−2 (mod p) (p∈P)a^{-1} \equiv a^{p-2}\ (mod\ p)\ (p\in\mathbb{P}) 。

一个快速幂就好了。

欧几里得算法和扩展欧几里得算法：

重要的公式：

gcd⁡(a,b)=gcd⁡(b,a mod b)\gcd(a,b) = \gcd(b,a\ mod\ b)

证明：令 gcd⁡(a,b)=d\gcd(a,b) = d ，则 a=x⋅da = x\cdot d ， b=y⋅db=y\cdot d ，且 gcd⁡(x,y)=1\gcd(x,y) = 1。

则 gcd⁡(a,b)=gcd⁡(x⋅d,y⋅d)=gcd⁡(y⋅d,(x mod y)⋅d)=gcd⁡(y⋅d,x⋅d mod y⋅d)=gcd⁡(b,a mod b)\gcd(a,b) = \gcd(x\cdot d, y\cdot d) = \gcd(y\cdot d, (x\ mod\ y)\cdot d) = \gcd(y\cdot d,x\cdot d\ mod\ y\cdot d) = \gcd(b,a\ mod\ b) 。

反复运用这一公式求出 gcd⁡(a,b)\gcd(a,b) 就是欧几里得算法。递归边界为 b=0b=0 ，时间复杂度为 O(log⁡min⁡(a,b))O(\log \min(a,b)) 。

P.S. 用迭代法常数更小哦。

接下来看扩展欧几里得算法，简称扩欧。

对于一个方程 ax+by=gcd⁡(a,b)ax+by = \gcd(a,b) 有无数个整数解。若求出解 (x0,y0)(x_0, y_0) ，任意解 (x,y)(x,y) 为：

x=x0+k⋅bgcd⁡(a,b), y=y0−k⋅agcd⁡(a,b), k∈Zx = x_0 + k\cdot \frac{b}{\gcd(a,b)}, \ y = y_0 - k\cdot \frac{a}{\gcd(a,b)},\ k\in\mathbb{Z}

任意解的推论是显然的。为什么存在 (x0,y0)(x_0,y_0) 呢？因为我们可以反复用到之前的那个公式。当 bb 最终等于 00 时，有一组解 x=1,y=0x=1,y=0 使得 ax+by=gcd⁡(a,b)ax+by=\gcd(a,b) 。我们递归回来的时候调整一下 x,yx,y 就可以找到一组解了。

递归时，已经知道使 bx1+(a mod b)y1=gcd⁡(a,b)bx_1 + (a\ mod\ b)y_1 = \gcd(a,b) 成立的 (x1,y1)(x_1,y_1) 了。

我们需要知道使 ax2+by2=gcd⁡(a,b)ax_2 + by_2 = \gcd(a,b) 成立的 (x2,y2)(x_2,y_2) 。

打开前一个方程：

bx1+(a mod b)y1=gcd⁡(a,b)bx_1 + (a\ mod\ b)y_1 = \gcd(a,b)

bx1+(a−⌊ab⌋⋅b)y1=gcd⁡(a,b)bx_1 + (a-\lfloor\frac{a}{b}\rfloor\cdot b)y_1 = \gcd(a,b)

ay1+b(x1−⌊ab⌋⋅y1)=gcd⁡(a,b)ay_1 + b(x_1-\lfloor\frac{a}{b}\rfloor\cdot y_1) = \gcd(a,b)

解得 x2=y1, y2=x1−⌊ab⌋⋅y1x_2 = y_1,\ y_2 = x_1-\lfloor\frac{a}{b}\rfloor\cdot y_1 。

Code:Code:

1
2
3
4
5
6
7
8
9
10
11
12
int exgcd(int a,int b,int& x,int& y){//这个可以顺便求出gcd(a,b)
	if (!b) return x=1,y=0,a;
	else{
		int d=exgcd(b,a%b,y,x);
		y-=a/b*x;
		return d;
	}
}
void exgcd(int a,int b,int& x,int& y){//这个是简约版
	if (!b) return x=1,y=0,void();
	else exgcd(b,a%b,y,x),y-=a/b*x,void();
}

扩展欧拉定理

我称之为降幂公式。

ab≡abmod  φ(p)+φ(p) (mod p)    (b≥φ(p))a^b \equiv a^{b\mod \varphi(p)+\varphi(p)}\ (mod\ p)\ \ \ \ (b\geq \varphi(p))

证明以后再写。