P3601 签到题
// 容易注意到 qiandao(i) = i - phi(i)// phi 是欧拉函数
// 让我们想起最开始求欧拉函数的做法
// 分解质因数, 然后使用 phi(x) = x * 求积_{p in {x 的所有质因数}} (1 - 1 / p)
// 这样的时间复杂度显然过大
// 我们何妨不反着思考
// 既然找到 l <= x <= r 的所有质因子不行, 不如考虑一个质因子是哪些 l <= x <= r 的质因子
#include <iostream>
#include <vector>
using namespace std;
template <typename T>
using vec = vector<T>;
#define int long long
const int N = 1e6 + 10;
vec<int> primes;
bool not_prime;
// 线性筛模板
void get_primes(int n) {
for (int i = 2; i <= n; i ++) {
if (!not_prime) {
primes.push_back(i);
}
for (int j : primes) {
if (i * j > n) break;
not_prime = true;
if (i % j == 0) {
break;
}
}
}
}
const int mod = 666623333;
int l, r;
vec<int> _pfactors;
// 方便写代码的映射
// pfactors(i) 为 i 的质因子们
#define pfactors(i) _pfactors[(i) - l]
signed main() {
get_primes(N - 5);
cin >> l >> r;
// 我们可以遍历所有质数 p < sqrt r
// 这里直接遍历所有 p < sqrt(r 的最大值) 了, 没差
// 为什么是 p < sqrt(r)?
// 对于一个数 x, 它的质因子中最多只会有一个大于 sqrt x
// 这个质因子可以由 x 除以所有其他质因子得到
// 可以想想分解质因数模板中为什么只用遍历到 sqrt x, 一个道理
for (int p : primes) {
// i 为 p 的 >= l 且 <= r 的倍数, 思想类似埃氏筛
for (int i = ((l - 1) / p + 1) * p; i <= r; i += p) {
pfactors(i).push_back(p);
}
}
int ans = 0;
for (int i = l; i <= r; i ++) {
// 下面一段就是分解质因数, 只不过原本是遍历所有 <= sqrt x
// 这里直接用提前求出来的 pfactors
int phi = i, x = i;
for (int p : pfactors(i)) {
phi = phi / p * (p - 1);
while (x % p == 0) x /= p;
}
// 唯一一个大于 > sqrt(x) 的因子, 和分解质因数模板一样
if (x != 1) phi = phi / x * (x - 1);
ans = (ans + i - phi) % mod;
}
cout << ans;
return 0;
}<br>来源：程序园用户自行投稿发布，如果侵权，请联系站长删除<br>免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ 用心讨论，共获提升！ 这个好，看起来很实用
页:
[1]