笔记汇总
欧拉函数的定义
1∼N 中与 N 互质的数的个数被称为欧拉函数，记为 φ(N)。
若在算数基本定理中，N=pa11∗pa22∗…∗pamm，则：
φ(N)=N×p1−1p1×p2−1p2×…×pm−1pm
证明 (proof)
定义 (definition)
互质：公约数只有 1 的两个整数互质
边界 (basis)
φ(1)=1，小于等于 1 的正整数只有 1，
稍微扩展一下 ∼hh
φ(1)=1， φ(2)=1， φ(3)=2
φ(4)=2， φ(5)=4， φ(6)=2
φ(7)=6， φ(8)=4， φ(9)=6
φ(10)=5，φ(11)=10，φ(12)=4
规律 1
可以发现，对于两个互质的数 m,n，满足 φ(mn)=φ(m)∗φ(n)，例如
φ(6)=φ(2)∗φ(3)=1∗2=2
φ(12)=φ(3)∗φ(4)=2∗2=4
这个性质很好证明：
如果一个数 d 与 n 互质，则 d 肯定也与 n∗m 互质。
若有一个数 c 与 n∗m 互质，则可以推论出 d∗c 同样与 n∗m 互质。
根据乘法原理可证。
规律 2
φ(ab)=ab−ab−1，例如
φ(4)=22−22−1=2
φ(9)=32−32−1=6
让我们来写一个优美的证明：
因为 φ(ab) 表示 从 1 到 ab 中与 ab 互质的数。
我们用排除法解决，在 φ(ab) 中，不与 ab 互质的数有 a、2a…ab−1∗a 共 ab−1 个数。
所以 φ(ab)=ab−ab−1，得证。
规律扩展
因为 N=pa11∗pa22∗…∗pamm
所以 φ(N)=φ(pa11)∗φ(pa22)∗…∗φ(pamm)
代入 φ(ab)=ab−ab−1 得
φ(N)=(pa11−pa1−11)∗(pa22−pa2−12)∗…∗(pamm−pam−1m)
又因为 ab−ab−1=ab∗(1−1a)
所以 φ(N)=pa11∗pa22∗…∗pamm∗(1−1p1)∗(1−1p2)∗…∗(1−1pm)=N∗m∏i=1(1−1pi)
得证。
性质 1
质数 的欧拉函数 等于 原值 −1，例如
φ(2)=1， φ(3)=2
φ(5)=4， φ(7)=6
因为 质数 与除其本身外的所有 小于它 的数互质
性质 2
设 d 为一个质数，其倍数为 kd
有 φ(d∗kd)=φ(kd)∗d
这是因为 φ(d∗kd) 中，不与 d∗kd 互质的数有 d、2d…d∗(kd) 共 kd 个数。
所以 φ(d∗kd)=d∗kd−(kd)=(d−1)∗kd=(kd−k)∗d=φ(kd)∗d
代码
试除法求欧拉函数
将 n 分解质因数，对于其质因数 pi，res=res∗1pi
其余同 分解质因数 。
时间复杂度： O(√n)
LL phi(int n)
{
LL res = n;
for (int i = 2; i <= n / i; i ++ )
if (n % i == 0)
{
res = res / i * (i - 1);
while (n % i == 0) n /= i; // 消除所有此质因子，一个质因子只记录一次
}
if (n > 1) res = res / n * (n - 1); // 消除小于 sqrt(n) 的质因子后还有质因子，就是大于 sqrt(n) 的
// 一个数最多只有一个大于 sqrt(n) 的质因子
return res;
}
筛法求欧拉函数
因为欧拉函数的关键是 分解质因数，所以可以直接套一个 线性筛。
对于一个 质数，其 欧拉函数 等于原值 −1。（性质 1）
又因为 质数 与除其 倍数 以外的任意自然数都 互质，
所以可以在 标记合数时 顺带计算合数的 欧拉函数（规律 1）
若 合数 与 质数 呈倍数关系时，有 φ(d∗kd)=φ(kd)∗d （性质 2）
时间复杂度： O(n)
void get_eulers(int n)
{
euler[1] = 1;
for (int i = 2; i <= n; i ++ )
{
if (!st[i])
{
primes[cnt ++ ] = i;
euler[i] = i - 1;
}
for (int j = 0; primes[j] <= n / i; j ++ )
{
int t = primes[j] * i;
st[t] = true;
if (i % primes[j] == 0)
{
euler[t] = euler[i] * primes[j];
break;
}
euler[t] = euler[i] * (primes[j] - 1);
}
}
}
区间内判断最大公约数为素数的方案数
本题要求的是 x,y<=n 时 gcd(x,y) 为质数的方案数。
因为 gcd 的结果不唯一，所以我们要进行化简。
设 p 为一个质数，则满足 gcd(x,y)=p 时，有 gcd(xp,yp)=1
由此将问题转化为解决 gcd(x,y)=1 的方案数，也就是 x 和 y 互质的方案数。
将 x 与 y 之间的关系分成两类 x>y 和 x<y。
对于其中任意一类，都可以转化为求出 1 到 n 中每个数的欧拉函数，
也就是当确定 x 的值时，计算 y 有多少种不同情况，令 x 和 y 互质。
值得注意的是，x=y 时，也为互质，这要进行特判。
用数组 s，统计前缀和 s[i]=s[i−1]+∗phi[i]
记得将预处理的数组转化为实际答案。
枚举质数 pi，将答案累计，注意其上界为 n/pi 下取整。
res+=2∗s[n/pi]+1
时间复杂度： O(n)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e7 + 10;
int n, m;
long long phi[N], p[N], v[N], s[N];
long long res;
inline bool check(int a, int b) // a % b 的常数优化
{
return a / b * b == a;
}
void init(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!v[i])
{
p[ ++ m] = i;
phi[i] = i - 1;
}
for (int j = 1; p[j] <= n / i; j ++ )
{
v[i * p[j]] = 1;
if (check(i, p[j]))
{
phi[i * p[j]] = phi[i] * p[j];
break;
}
phi[i * p[j]] = phi[i] * (p[j] - 1);
}
}
for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + phi[i]; // 前缀和
for (int i = 1; i <= m; i ++ ) res = res + s[n / p[i]] * 2 + 1; // 两种情况加特殊
}
int main()
{
scanf("%d", &n);
init(n);
printf("%lld", res);
}
