定义
给定正整数,求,
即
- 小于等于 且
- 与互质
的正整数个数。
性质
- , 如果 , 则
证明
证明性质1
求证:
由质数的定义可知,小于等于 且 与互质的数,在中,除了 以外均满足!
注:
证明性质2
求证:
首先,易知
, 即 中 unit(存在关于乘法逆元的元素)的数量
因为
所以
的units , 与
的 units
之间存在一个 bijection, 即
所以
注:
- 的证明见 这里
- 更严格的证明需要用到抽代里的中国剩余定理 (以Ring和Ideal表示的)
证明性质3
求证:
,所有与它不互质的数必然包含这个质数因子,因此满足条件的为:,共 个。
所以,与互质的数共有 个。
证明性质4
求证:
因为 ,且都是质数(所以两两互质)
由性质2,
由性质3,
所以
证明性质5
求证:, 如果 , 则
因为 ,
由性质2,
由性质3, , 我们可以推出
因为 ,由上可得出
即
求单个数的欧拉函数值
,直接质因数分解,由性质4即可求出!
时间复杂度:
代码
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
是当前用到的质数)
-
如果 i % p == 0
,说明 i * p
这个数里,包含了至少2个质因子 (即)。
由性质5,有
-
如果 i % p != 0
,说明 。
由性质2,有
时间复杂度:
代码
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; }
|
例题
题意
给定两个正整数 , , 求满足以下条件的 的数量?
其中,
题解
设 ,则 ,所以 且 ,又因为 ,所以
所以问题转化为:
设 ,求 ,使得 满足: 的 的数量?
我们会发现当 时,因为 ,所以我们可以将 的这一段,映射到 上。

所以最后我们要求的就是: 使得 ,所以满足条件的 的数量就等于
题意
给定一个 个节点的图 ,初始状态下图中没有边。
我们在一次操作中,可以选定任意一个正整数 ,往图中添加恰好 条边。一条边如果连接的是点 ,那么必须满足 。
图中不能出现自环和重边。
给定整数 ,求最少需要几次操作,使得图中边的数量恰好为 ?如果不存在,输出 。
其中,。
题解
先考虑 :有多少个点对 满足 ?
注意到 且 。
所以要求 的点对数量,令 。
则我们所求的变成 中互质的数对的数量。
形式化的,求:
注意到如果我们固定 ,那么里面那层求和就是欧拉函数 ,也就是求
这个预处理出来就可以了。
接下来考虑最少加几次边可以得到 ?
超级大所以没法背包。但注意到对于每一个 ,我们都至少可以加一次。
有了这个性质,说明只要 小于等于最大可能加的边数,就一定有解(可以理解成 这种构成了二进制的basis,覆盖了所有数,那这个更密集的 一定也可以)。
所以贪心的从大往小加,就可以得到最少加边次数了。
代码
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--) { ll r = min(cnt[k], m) / (k-1); 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); } }
|
参考链接
- https://blog.csdn.net/paxhujing/article/details/51353672
- https://www.luogu.com.cn/blog/JustinRochester/solution-p2158
- https://blog.nowcoder.net/n/0cbf747dc0874027b5c48cf7fbf27060
后记
写这篇文章的时候出了几个数学公式上的问题:
- 如果排版炸了,可以试着在
_
的前面加上 \
Author
tom0727
LastMod
2025-05-13
(9b93246)
,更新历史
License
CC BY-SA 4.0