题解：SP22382 ETFD - Euler Totient Function Depth
题目链接：link，点击这里喵。
前置知识：
【模板】线性筛素数，欧拉函数，点击这里喵。
题意简述：
给定整数 $l,r,k$，求出 $$ 中有多少个整数不断对自己取欧拉函数刚好 $k$ 次结果为 $1$。
思路：
看眼数据范围，$10^{10}$ 的量级显然不容我们每次暴力，故考虑预处理 $\varphi(i),can(i,k),sum(i,k)$。定义如其名。
做法：
1. 预处理 $\varphi(i)$：
这里采用线性筛，这里在注释中简要说明，证明过程详见：筛法求欧拉函数。
void get_phi(const int n){
bool isprime;
memset(isprime,1,sizeof(isprime));
phi=1;isprime=isprime=0;
vector<int> prime;
for(int i=2;i<n;++i){
if(isprime){phi=i-1;prime.push_back(i);} //当 i 为质数时，小于她且与之互质的显然有 (i-1) 个
for(auto e: prime){
if(e*i>=n){break;}
isprime=0;
if(i%e==0){phi=phi*e;break;} //当 i 中含有 e 这个质因子时，phi(i * e) = phi(i) * e
phi=phi*phi; //当 i 中不含有 e 这个质因子时，phi(i * e) = phi(i) * (e-1)
}
}
}2. 预处理 $can(i,k)$ 以及 $sum(i,k)$：
唯一要注意的点是，是恰好 $k$ 次，所以尽管 $\varphi(1)=1$，仍然不能无限套娃，这点在求 $sum(i,k)$ 时一定要注意。
sum=can=1;for(int i=2;i 谢谢分享，辛苦了 感谢分享，下载保存了，貌似很强大 感谢分享，下载保存了，貌似很强大 很好很强大我过来先占个楼 待编辑 热心回复！ 东西不错很实用谢谢分享 过来提前占个楼 热心回复！ 收藏一下 不知道什么时候能用到 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 分享、互助 让互联网精神温暖你我 谢谢楼主提供！ 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 收藏一下 不知道什么时候能用到 感谢分享，学习下。 这个好，看起来很实用 这个好，看起来很实用 谢谢楼主提供！ 感谢分享
页:
[1]
2