题解：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]