题解：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)$：

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

<code>void get_phi(const int n){

bool isprime[n];

memset(isprime,1,sizeof(isprime));

phi[1]=1;isprime[0]=isprime[1]=0;

vector<int> prime;

for(int i=2;i<n;++i){

if(isprime[i]){phi[i]=i-1;prime.push_back(i);} //当 i 为质数时，小于她且与之互质的显然有 (i-1) 个

for(auto e: prime){

if(e*i>=n){break;}

isprime[e*i]=0;

if(i%e==0){phi[i*e]=phi[i]*e;break;} //当 i 中含有 e 这个质因子时，phi(i * e) = phi(i) * e

phi[i*e]=phi[i]*phi[e]; //当 i 中不含有 e 这个质因子时，phi(i * e) = phi(i) * (e-1)

}

}

}

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

唯一要注意的点是，是恰好 $k$ 次，所以尽管 $\varphi(1)=1$，仍然不能无限套娃，这点在求 $sum(i,k)$ 时一定要注意。

sum[1][0]=can[1][0]=1;

for(int i=2;i<N;++i){

for(int e=0;e<21;++e){

can[i][e]=can[phi[i]][e-1];

sum[i][e]=sum[i-1][e]+can[i][e];

}

}

小贴士：

请万分注意 $sum(i,k)$ 的求值过程。

时间复杂度分析：

预处理 $O(kn)$，查询 $O(T)$，总体之间复杂度 $O(kn)$。

代码:

#include <stdio.h>

#include <ctype.h>

#include <algorithm>

#include <string.h>

#include <vector>

#define lnt long long

#define dnt double

#define inf 0x3f3f3f3f

using namespace std;

int xx;char ff,chh;inline int read(){

xx=ff=0;while(!isdigit(chh)){if(chh=='-'){ff=1;}chh=getchar();}

while(isdigit(chh)){xx=(xx<<1)+(xx<<3)+chh-'0';chh=getchar();}return ff? -xx: xx;

}

const int N=1e6+2e4;

int phi[N];

int can[N][22],sum[N][22];

void get_phi(const int);

int main(){

get_phi(N);

sum[1][0]=can[1][0]=1;

for(int i=2;i<N;++i){ //从 2 开始避免无线套娃

for(int e=0;e<21;++e){

can[i][e]=can[phi[i]][e-1];

sum[i][e]=sum[i-1][e]+can[i][e];

}

}

int G=read();

while(G--){

int l=read(),r=read(),k=read();

printf("%d\n",sum[r][k]-sum[l-1][k]);

}

return 0;

}

void get_phi(const int n){

bool isprime[N];

memset(isprime,1,sizeof(isprime));

phi[1]=1;isprime[0]=isprime[1]=0;

vector<int> prime;

for(int i=2;i<n;++i){

if(isprime[i]){phi[i]=i-1;prime.push_back(i);}

for(auto e: prime){

if(e*i>=n){break;}

isprime[e*i]=0;

if(i%e==0){phi[i*e]=phi[i]*e;break;} //线性筛减免时间复杂度的核心操作

phi[i*e]=phi[i]*phi[e];

}

}

}

公式真的没有中文标点了