【数论】—— 欧拉函数

欧拉函数

在做关于素数的题目时经常需要用到关于欧拉函数的知识，并且求法相似，所以建议先看我的素数 blog。

求单个数的欧拉函数

定义

对于任意正整数 $n$，欧拉函数 $\phi (n)$ 表示在不大于 $n$ 的正整数中与 $n$ 互素的数的个数。

举几个例子：

• $\phi (1)=1$，即 $1$。
• $\phi (6)=2$，即 $1$，$5$。
• $\phi (12)=4$，即 $1$，$5$，$7$，$11$。

怎样求出一个数的欧拉函数呢？公式呈上：

对于任意正整数 $n$，若 $n=P_1^{k_1}\times P_2^{k_2}\times \cdots \times P_m^{k_m}$。则有 $\phi (n)=n\times (1-\frac{1}{P_1})\times (1-\frac{1}{P_2})\times \cdots \times (1-\frac{1}{P_m})$。

化简得：$\phi (n)={\prod }_{i=1}^m(1-\frac{1}{p_i})$。

有这个公式，我们可以求出单个正整数的欧拉函数。即在分解素因数时计算欧拉函数。

时间复杂度：$O(\sqrt{n})$。

代码

注意：在素因数分解完后如果 $n$ 变成了素数，那 $ans$ 还要再运算一次。

inline int phi(int n) {
	int ans = n;
	for(register int i = 2;i <= sqrt(n);i ++)
		if(n % i == 0) {
			ans = ans / i * (i - 1);
			while (n % i == 0)
				n /= i;
		}
	if(n > 1)
		ans = ans / n * (n - 1);
	return ans;
}

欧拉函数公式的推导过程

接下来，我们一起推导在 $O(\sqrt{n})$ 时间内求出欧拉函数的公式。

首先要知道几个性质：

1. 对于任意素数 $x$，有 $\phi (x)=x-1$。这个很好理解，即 $x$ 与所有小于它的数互素。

2. 对于任意素数 $p$，有 $\phi (p^k)=p^k-p^{k-1}$。为什么呢？

   证明：因为 $p$ 是素数，所以 $p^k$ 的素因数只含有 $p$。那么在小于等于 $p^k$ 的数中与其不互素的数便是 $p$，$2\times p$，$3\times p$，$\cdots$，$p^{k-1}\times p$，共 $p^{k-1}$ 个。得证。

3. 欧拉函数是积性函数，但不是完全积性函数。这意味着 $\phi (m\times n)=\phi (m)\times \phi (n)$ 成立的前提是 $\gcd (m,n)=1$。

了解完这几个性质后，我们开始推导：

设 $N=p_1^{k_1}\times p_2^{k_2}\times p_3^{k_3}\times \cdots \times p_n^{k_n}$。

因为 $p_1,p_2,p_3,\cdots ,p_n$ 都是素数，所以 $p_1^{k_1}，p_2^{k_2}，\cdots ，p_n^{k_n}$ 两两互素。

所以由性质 3 得：

$$\phi (N)=\phi (p_1^{k_1})\times \phi (p_2^{k_2})\times \cdots \times \phi (p_n^{k_n})$$

再由性质 2 得：

$$\phi (N)=(p_1^{k_1}-p_1^{k_1-1})\times (p_2^{k_2}-p_2^{k_2-1})\times \cdots \times (p_n^{k_n}-p_n^{k_n-1})$$

提取公因数得：

$$\phi (N)=p_1^{k_1}\times p_2^{k_2}\times \cdots \times p_n^{k_2}\times (1-\frac{1}{p_1})\times (1-\frac{1}{p_2})\times \cdots \times (1-\frac{1}{p_n})$$

最后把前 $n$ 项合并一下便得到：

$$\phi (N)=N\times (1-\frac{1}{p_1})\times (1-\frac{1}{p_2})\times \cdots \times (1-\frac{1}{p_n})$$

推导完毕。

欧拉函数的线性筛法

和素数一样，这样的算法求单个数的欧拉函数时间复杂度很优，但当题目需要求一串数的欧拉函数时便处理不了了。此时的时间复杂度便是 $O(n\sqrt{n})$。

那求一串数欧拉函数是否和求素数一样，有跟快甚至线性的方法呢？当然有，由刚刚的几个性质，我们可以在线性筛的基础上改进，在 $O(n)$ 的时间内求得每个数的欧拉函数。

这里我们需要再引入一个性质：

4. 若 $i\mathrm{mod}p=0$，则有：$\phi (p\times i)=\phi (i)\times p$。

   证明：

   设 $b=\gcd (n,i)$；

   因为 $n$，$i$ 不互素，所以 $n=k_{1}b$，$i=k_{2}b$。

   因为 $n+i=(k_1+k_2)b$，所以 $n+i$ 与 $i$ 不互素。

   $[1,i]$ 中与 $i$ 不互素的整数 $n$ 共 $i-\phi (i)$ 个。

   因为 $n+i$ 与 $i$ 不互素，所以 $[1+i,i+i]$，即 $(i,2i]$ 中与 $i$ 不互素的整数也是 $i-\phi (i)$ 个，所以 $[1,i+p]$ 中与 $i$ 不互素的整数 $p\times i-p\times \phi (i)$ 个。

   因为 $i\mathrm{mod}p=0$，$i$ 与 $p$ 没有不同的因数，$[1,i\times p]$ 中与 $i\times p$ 不互素的整数数量 $p\times i-p\times \phi (i)=i\times p-\phi (i\times p)$。

   所以：$\phi (i\times p)=p\times \phi (i)$。

我们一起边回顾线性筛代码，边了解求欧拉函数的方法：

定义phi[MAXN]存储欧拉函数。

首先，在开始筛之前我们先需要特判 $1$ 的情况。同样，在求欧拉函数时，要先把 $\phi (1)$ 赋值为 $1$。

 is_prime[1] = true;
 phi[1] = 1;

然后我们开始找素数。在找的过程中，如果遇到了素数 $x$，那我们就存储下 $x$。同时，由之前讲的性质 $1$ 得 $\phi (x)=x-1$。所以我们便可以对它的欧拉函数进行赋值。

for(register int i = 2;i <= n;i ++) {
	if(!is_prime[i]) {
		prime[++ cnt] = i;
		phi[i] = i - 1;
	}
	...
}

最后，在用找到的数 $x$ 来筛素数的过程中。

若用来与 $x$ 相乘的素数 $y$ 不是 $x$ 的最小的素因数，即比 $x$ 的最小的素因数小，则说明 $x$ 不包含 $y$ 这个素因数，所以 $\gcd (x,y)=1$。此时，由性质 $3$ 得到：$\phi (x\times y)=\phi (x)\times \phi (y)$。

若用来与 $x$ 相乘的素数 $y$ 已经与 $x$ 不互素了，即此时 $y$ 是 $x$ 的最小素因数。则根据性质 $4$ ，有：$\phi (x\times y)=\phi (x)\times y$。

for(register int j = 1; j <= cnt , i * prime[j] <= n; j ++) {
	is_prime[i * prime[j]] = true;
	if(i % prime[j] == 0) {
		phi[i * prime[j]] = phi[i] * prime[j];
		break;
	}
	phi[i * prime[j]] = phi[i] * phi[prime[j]];
}

完整代码

int phi[MAXN] , prime[MAXN] , cnt;
bool is_prime[MAXN];

inline void Init_phi(int n) {
	is_prime[1] = true;
	phi[1] = 1;
	for(register int i = 2;i <= n;i ++) {
		if(!is_prime[i]) {
			prime[++ cnt] = i;
			phi[i] = i - 1;
		}
		for(register int j = 1;j <= cnt , i * prime[j] <= n;j ++) {
			is_prime[i * prime[j]] = true;
			if(i % prime[j] == 0) {
				phi[i * prime[j]] = phi[i] * prime[j];
				break;
			}
			phi[i * prime[j]] = phi[i] * phi[prime[j]];
		}
	}
	return;
}