P3601 签到题

1. // 容易注意到 qiandao(i) = i - phi(i)
2. // phi 是欧拉函数
4. // 让我们想起最开始求欧拉函数的做法
5. // 分解质因数, 然后使用 phi(x) = x * 求积_{p in {x 的所有质因数}} (1 - 1 / p)
6. // 这样的时间复杂度显然过大
8. // 我们何妨不反着思考
9. // 既然找到 l <= x <= r 的所有质因子不行, 不如考虑一个质因子是哪些 l <= x <= r 的质因子
11. #include <iostream>
12. #include <vector>
13. using namespace std;
14. template <typename T>
15. using vec = vector<T>;
17. #define int long long
19. const int N = 1e6 + 10;
20. vec<int> primes;
21. bool not_prime[N];
23. // 线性筛模板
24. void get_primes(int n) {
25. for (int i = 2; i <= n; i ++) {
26. if (!not_prime[i]) {
27. primes.push_back(i);
28. }
29. for (int j : primes) {
30. if (i * j > n) break;
31. not_prime[i * j] = true;
32. if (i % j == 0) {
33. break;
34. }
35. }
36. }
37. }
39. const int mod = 666623333;
41. int l, r;
43. vec<int> _pfactors[N];
45. // 方便写代码的映射
46. // pfactors(i) 为 i 的质因子们
47. #define pfactors(i) _pfactors[(i) - l]
49. signed main() {
50. get_primes(N - 5);
51. cin >> l >> r;
54. // 我们可以遍历所有质数 p < sqrt r
55. // 这里直接遍历所有 p < sqrt(r 的最大值) 了, 没差
57. // 为什么是 p < sqrt(r)?
58. // 对于一个数 x, 它的质因子中最多只会有一个大于 sqrt x
59. // 这个质因子可以由 x 除以所有其他质因子得到
60. // 可以想想分解质因数模板中为什么只用遍历到 sqrt x, 一个道理
61. for (int p : primes) {
62. // i 为 p 的 >= l 且 <= r 的倍数, 思想类似埃氏筛
63. for (int i = ((l - 1) / p + 1) * p; i <= r; i += p) {
64. pfactors(i).push_back(p);
65. }
66. }
68. int ans = 0;
69. for (int i = l; i <= r; i ++) {
70. // 下面一段就是分解质因数, 只不过原本是遍历所有 <= sqrt x
71. // 这里直接用提前求出来的 pfactors
72. int phi = i, x = i;
73. for (int p : pfactors(i)) {
74. phi = phi / p * (p - 1);
75. while (x % p == 0) x /= p;
76. }
77. // 唯一一个大于 > sqrt(x) 的因子, 和分解质因数模板一样
78. if (x != 1) phi = phi / x * (x - 1);
79. ans = (ans + i - phi) % mod;
80. }
82. cout << ans;
84. return 0;
85. }

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

用心讨论，共获提升！

这个好，看起来很实用