---

线性筛法构造欧拉函数表

欧拉函数 $\phi(n)$

• 了解欧拉函数

  欧拉函数的值描述了区间 $[1, n]$ 内与 $n$ 互质的整数的个数
  例如$\phi(3)=2,\phi(4)=2,\phi(5)=4$
  同时，定义 $\phi(n)=1$

  欧拉函数的常用性质：

  1. 若$n$为质数，则$\phi(n)=n-1$
  2. 为积性函数，即若$m,n$互质，则$\phi(mn)=\phi(m)\phi(n)$ $\color{red}{\star\star\star}$
  3. 由2：若$p$为质数，且$n=p^k$，则$\phi(n)=(p-1)p^{k-1}=p^k-p^{k-1}$

• 求欧拉函数值

  1. 通过筛法打素数表，短除法分解质因数，通过欧拉函数公式计算
  2. 筛法构造欧拉函数表 $\color{red}{\star\star\star}$

  筛法求欧拉函数值的原理

  欧拉函数的线性筛用到了两条性质：

  • $\phi(mn)=\phi(m)\phi(n)$ （$gcd(m,n)=1$）
  • $\phi(p^{k+1})=p×\phi(p^k)$（由性质1、2推出）
    结论公式：

  $$\color{purple} \phi(i×p_j)=\begin{cases} \phi(i)×(p_j-1) & (p_j\nmid i) \\ \phi(i)×p_j & (p_j\mid i) \end{cases}$$

  $$i \geq p_j,p_j\in P$$

筛法的程序实现

欧拉函数表筛法与欧拉筛的步骤极度相似，点击这里先了解一下欧拉筛的原理

先贴代码：

int p[maxn], phi[maxn], cnt = 0;

void eularfunc(int n) {
	memset(p, 0, sizeof(p));
	memset(phi, 0, sizeof(phi));
	phi[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (!phi[i])
			p[++cnt] = i, phi[i] = i - 1;
		for (int j = 1; j <= cnt && i * p[j] <= n; j++) {
			count[i * p[j]]++;
			if (i % p[j] == 0) {
				phi[i * p[j]] = phi[i] * p[j];
				break;
			}
			else {
				phi[i * p[j]] = phi[i] * (p[j] - 1);
			}
		}
	}
}

为了方便对比，欧拉筛也贴上：

bool isPrime[maxn];
int Prime[maxn], cnt = 0;

void eular(int n) {
    memset(isPrime, true, sizeof(isPrime));
    memset(Prime, 0, sizeof(Prime));
    isPrime[1] = 0;
    for(int i = 2; i <= n; i++) {
        if(isPrime[i]) 
            Prime[++cnt] = i;
        for(int j = 1; j <= cnt && i*Prime[j] <= n; j++) {
            isPrime[i * Prime[j]] = 0;
            if(i % Prime[j] == 0)
                break;
        }
    }
}

然后发现——它们的程序结构非常相似！！

简解：

从筛算法所用的欧拉函数公式上看，无非就是在欧拉筛的基础上再添加了一层映射后，略微调整了计算方法，也可以将$\phi$看作一个数组，$i$是它的下标。可以说，欧拉函数筛无非就是欧拉素数筛的变形。

参考对欧拉素数筛正确性的证明，可以简单地证明欧拉函数筛可以不重不漏地计算出范围内所有数字对应的函数值。

这里还要补充一下，在计算$\phi (i×p_j)$时，我们必须要先知道$\phi(i)$的值，下面证明它的已知性：

• 当$i$是素数时，$\phi(i)=i-1$，已知

• 当$i$是合数时，假设$p_0$为$i$的最小质因子，那么一定有$i=p_0×k$ $(k<i)$

  在循环中到$k$时，假设$p_1$是$k$的最小质因子，那么必有$p_1 \geq p_0$

  所以在小于$k$的素数时一定会遍历到$p_0$，即一定会出现计算$\phi(p_0×k)$的操作

  那么$\phi(i)$一定已知

综上，在计算$\phi (i×p_j)$时，$\phi(i)$已知

练习题

洛谷P2158 [SDOI]仪仗队

题目描述

作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。

现在，C君希望你告诉他队伍整齐时能看到的学生人数。

输入格式

共一个数N

输出格式

共一个数，即C君应看到的学生人数。

输入输出样例

组别	输入	输出
1	4	9

说明/提示

【数据规模和约定】
对于 100% 的数据，1 ≤ N ≤ 40000

解析

首先我们来考虑什么位置的同学看不到（被能看到的人挡住）。为了更好的描述位置，我们把方阵放在坐标系里，C君的坐标为$(0, 0)$，水平向左是$x$正半轴，竖直向上是$y$正半轴，坐标最大为$\color{red}n-1$。

容易发现，假设C君看不到A君$(x_A, y_A)$，那么一定有个B君挡住了A君，即A的坐标一定是B的坐标的“倍数”。抽象一下，如果A君被挡住，那么：

反之，当且仅当$gcd(x_A,y_A)=1$时，A君可以被C君看见。

现在，我们可以总结出这题的数学模型：

稍微分类讨论一下，满足$gcd(x,y)=1$的元素，有下面几类：

1. $x>y$，显然有$\sum_{i=1}^{n-1}\phi(i)$个（$\phi(n)$为欧拉函数）
2. $x=y$，只有$(1,1)$
3. $x<y$，同“1”，有$\sum_{i=1}^{n-1}\phi(i)$个

三类求总和。综上，本题答案$\color{red}ans(n)=2\sum_{i=1}^{n-1}\phi(i)+1$（别忘了特判$n=0$）

全部问题迎刃而解，贴代码！！

#include <iostream>
#include <cstring>

using namespace std;

int p[40010], phi[40010], cnt = 0;

void eularfunc(int n) {
	memset(p, true, sizeof(p));
	memset(phi, 0, sizeof(phi));
	phi[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (!phi[i])
			p[++cnt] = i, phi[i] = i - 1;
		for (int j = 1; j <= cnt && i * p[j] <= n; j++) {
			if (i % p[j] == 0) {
				phi[i * p[j]] = phi[i] * p[j];
				break;
			}
			else {
				phi[i * p[j]] = phi[i] * (p[j] - 1);
			}
		}
	}
}

long long sum(int n) {
	long long s = 0;
	for (int i = 1; i <= n; i++) 
		s += phi[i];
	return s;
}

int main() {
	int n;
	cin >> n;
	eularfunc(n);
	if (n == 1) cout << 0;
	else cout << 2 * sum(n - 1) + 1;
	return 0;
} 

 

起笔2020年新年第一天，落笔2020年1月26号（第二天）

标签