题解：SP22382 ETFD - Euler Totient Function Depth

题目链接：

link，点击这里喵。
前置知识：

【模板】线性筛素数，欧拉函数，点击这里喵。
题意简述：

给定整数 $l,r,k$，求出 $[l,r]$ 中有多少个整数不断对本身取欧拉函数刚好 $k$ 次结果为 $1$。
思路：

看眼数据范围，$10^{10}$ 的量级显然不容我们每次暴力，故思量预处理 $\varphi(i),can(i,k),sum(i,k)$。定义如其名。
做法：

1. 预处理 $\varphi(i)$：

这里采用线性筛，这里在注释中简要说明，证实过程详见：筛法求欧拉函数。

1. void get_phi(const int n){
2.         bool isprime[n];
3.         memset(isprime,1,sizeof(isprime));
4.         phi[1]=1;isprime[0]=isprime[1]=0;
5.         vector<int> prime;
6.         for(int i=2;i<n;++i){
7.                 if(isprime[i]){phi[i]=i-1;prime.push_back(i);}      //当 i 为质数时，小于她且与之互质的显然有 (i-1) 个
8.                 for(auto e: prime){
9.                         if(e*i>=n){break;}
10.                         isprime[e*i]=0;
11.                         if(i%e==0){phi[i*e]=phi[i]*e;break;}            //当 i 中含有 e 这个质因子时，phi(i * e) = phi(i) * e
12.                         phi[i*e]=phi[i]*phi[e];                         //当 i 中不含有 e 这个质因子时，phi(i * e) = phi(i) * (e-1)
13.                 }
14.         }
15. }

复制代码

2. 预处理 $can(i,k)$ 以及 $sum(i,k)$：

唯一要留意的点是，是恰恰 $k$ 次，以是尽管 $\varphi(1)=1$，仍然不能无限套娃，这点在求 $sum(i,k)$ 时一定要留意。
[code]sum[1][0]=can[1][0]=1;for(int i=2;i