定义

给定正整数n,求φ(n), 即

  1. 小于等于n
  2. n互质

的正整数个数。

性质

  1. φ(p)=p1, prime p
  2. φ(mn)=φ(m)φ(n)gcd(m,n)=1
  3. φ(pk)=pkpk1=pk(11p)
  4. n=p1k1p2k2prkr, φ(n)=ni=1r(11pi)=n(11p1)(11p2)(11pr)
  5. n=p1k1p2k2prkr, 如果   i, s.t. ki>1, 则 φ(n)=φ(npi)pi

证明

证明性质1

求证: φ(p)=p1, prime p

由质数的定义可知,小于等于p 且 与p互质的数,在[1,p]中,除了 p以外均满足!

注: φ(1)=1

证明性质2

求证: φ(mn)=φ(m)φ(n)gcd(m,n)=1

首先,易知 φ(n)=|Zn×| , 即 Znunit(存在关于mod n乘法逆元的元素)的数量

因为 ZmnZm×Zngcd(m,n)=1

所以 Zmn的units Zmn× , 与
Zm×Zn的 units (Zm×Zn)× 之间存在一个 bijection, 即

Zmn×(Zm×Zn)×=Zm××Zn×

所以 φ(mn)=|Zmn×|=|Zm××Zn×|=|Zm×||Zn×|=φ(m)φ(n)

注:

  1. ZmnZm×Zngcd(m,n)=1 的证明见 这里
  2. 更严格的证明需要用到抽代里的中国剩余定理 (以Ring和Ideal表示的)
证明性质3

求证:φ(pk)=pkpk1=pk(11p)

n=pk,所有与它不互质的数m必然包含p这个质数因子,因此满足条件的m为:1p,2p,3p,,pk1p,共 pk1个。

所以,与n=pk互质的数共有 pkpk1个。

证明性质4

求证:n=p1k1p2k2prkr, φ(n)=ni=1r(11pi)=n(11p1)(11p2)(11pr)

因为 n=p1k1p2k2prkr,且p1,p2,,pr都是质数(所以两两互质)

由性质2, φ(n)=φ(p1k1)φ(p2k2)φ(prkr)

由性质3,φ(piki)=pikipiki1=piki(11pi)

所以 φ(n)=p1k1p2k2prkr(11p1)(11p2)(11pr)=n(11p1)(11p2)(11pr)

证明性质5

求证:n=p1k1p2k2prkr, 如果   i, s.t. ki>1, 则 φ(n)=φ(npi)pi

因为 n=p1k1p2k2prkr

由性质2,φ(n)=φ(p1k1)φ(p2k2)φ(prkr)

由性质3, φ(pk)=pkpk1, 我们可以推出 φ(pk+1)=φ(pk)p

因为   i, s.t. ki>1,由上可得出 φ(piki)=φ(piki1)pi

φ(n)=φ(p1k1)φ(p2k2)(φ(piki1)pi)φ(prkr)=φ(npi)pi

求单个数的欧拉函数值

n=p1k1p2k2prkr,直接质因数分解,由性质4即可求出!

时间复杂度:O(n)

代码

copy
1
2
3
4
5
6
7
8
9
10
11
ll phi(ll x) {
ll res = x;
for (ll p = 2; p * p <= x; p++) {
if (x % p == 0) {
res = (res / p) * (p-1);
}
while (x % p == 0) x /= p;
}
if (x > 1) res = res / x * (x-1);
return res;
}

线性筛求1~n的欧拉函数值

和线性筛的基本思路一样,只不过要分类讨论 i % p == 0 与否。(i是当前处理到的数, p是当前用到的质数)

  1. 如果 i % p == 0,说明 i * p 这个数里,包含了至少2个质因子p (即p2)。

    由性质5,有 φ(ip)=φ(i)p

  2. 如果 i % p != 0,说明 gcd(i,p)=1

    由性质2,有 φ(ip)=φ(i)φ(p)

时间复杂度: O(n)

代码

luogu-P2158-AC代码

题目链接: https://www.luogu.com.cn/problem/P2158

copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244352;
const int maxn = 4e4+5;
int phi[maxn];
bool p[maxn];
vector<int> primes;
int main() {
int n; cin >> n;
if (n <= 1) {
cout << 0 << endl;
return 0;
}
phi[1] = 1;
fill(p, p+maxn, 1);
for (int i = 2; i <= n; i++) {
if (p[i]) {
phi[i] = i-1;
primes.push_back(i);
}
for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
int cur = primes[j];
p[i*cur] = 0;
if (i % cur == 0) {
phi[i*cur] = phi[i] * cur;
break;
} else {
phi[i*cur] = phi[i] * phi[cur];
}
}
}
int ans = 3;
for (int i = 2; i <= n-1; i++) ans += 2*phi[i];
cout << ans << endl;
}

例题

例1 CF1295D

题意

给定两个正整数 a, m, 求满足以下条件的 x 的数量?

  1. 0x<m
  2. gcd(a,m)=gcd(a+x,m)

其中,1a<m1010

题解

g=gcd(a,m),则 g=gcd(a+x,m),所以 gcd(a+xg,mg)=1  g|(a+x),又因为 g|a,所以  g|x

所以问题转化为:

c=ag,x=mg,求 k[c,c+x),使得 k 满足:gcd(x,k)=1k 的数量?

我们会发现当 k>x 时,因为 gcd(x,k)=gcd(x,kx),所以我们可以将 k(x,c+x) 的这一段,映射到 k(0,c) 上。

image

所以最后我们要求的k就是: k[1,x] 使得 gcd(k,x)=1,所以满足条件的 k 的数量就等于 φ(x)

例2 CF1731E. Graph Cost

题意

给定一个 n 个节点的图 1,2,,n,初始状态下图中没有边。

我们在一次操作中,可以选定任意一个正整数 k,往图中添加恰好 k 条边。一条边如果连接的是点 i,j,那么必须满足 gcd(i,j)=k+1

图中不能出现自环和重边。

给定整数 m,求最少需要几次操作,使得图中边的数量恰好为 m?如果不存在,输出 1

其中,n106,mn(n1)2

题解

先考虑 f(k):有多少个点对 i<j 满足 gcd(i,j)=k

注意到 gcd(i,j)=ki=ak,j=bkgcd(a,b)=1

所以要求 gcd(i,j)=k 的点对数量,令 m=nk

则我们所求的变成 1m 中互质的数对的数量。

形式化的,求:

i=1mj=1i1[1|gcd(i,j)=1]

注意到如果我们固定 i,那么里面那层求和就是欧拉函数 ϕ(i),也就是求

i=1mϕ(i)

这个预处理出来就可以了。


接下来考虑最少加几次边可以得到 m

m 超级大所以没法背包。但注意到对于每一个 k,我们都至少可以加一次

有了这个性质,说明只要 m 小于等于最大可能加的边数,就一定有解(可以理解成 1,2,4,8 这种构成了二进制的basis,覆盖了所有数,那这个更密集的 k 一定也可以)。

所以贪心的从大往小加,就可以得到最少加边次数了。

代码
copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
const int M = 1e6;
int phi[maxn];
ll sum_phi[maxn];
bool p[maxn];
vector<int> primes;
ll cnt[maxn];
void solve(int n, ll m) {
for (int k = 2; k <= n; k++) {
cnt[k] = sum_phi[n/k];
}
ll ans = 0;
for (int k = n; k >= 2; k--) {
// weight = k, cost = k, add (k-1) edges
ll r = min(cnt[k], m) / (k-1); // 拿了 r 次
ans += r * k;
m -= r * (k-1);
if (!m) {
cout << ans << "\n";
return;
}
}
cout << -1 << "\n";
}
int main() {
int T; cin >> T;
phi[1] = 0;
fill(p, p+maxn, 1);
for (int i = 2; i <= M; i++) {
if (p[i]) {
phi[i] = i-1;
primes.push_back(i);
}
for (int j = 0; j < primes.size() && i * primes[j] <= M; j++) {
int cur = primes[j];
p[i*cur] = 0;
if (i % cur == 0) {
phi[i*cur] = phi[i] * cur;
break;
} else {
phi[i*cur] = phi[i] * phi[cur];
}
}
}
for (int i = 1; i <= M; i++) {
sum_phi[i] = sum_phi[i-1] + phi[i];
}
while (T--) {
int n; ll m; cin >> n >> m;
solve(n, m);
}
}

参考链接

  1. https://blog.csdn.net/paxhujing/article/details/51353672
  2. https://www.luogu.com.cn/blog/JustinRochester/solution-p2158
  3. https://blog.nowcoder.net/n/0cbf747dc0874027b5c48cf7fbf27060

后记

写这篇文章的时候出了几个数学公式上的问题:

  1. 如果排版炸了,可以试着在 _ 的前面加上 \