MT头条

题解：SP22382 ETFD - Euler Totient Function Depth

2024-08-25 19:47 由 dongzhen 发表于 #后端开发

题目链接：

link，点击这里喵。

前置知识：

【模板】线性筛素数，欧拉函数，点击这里喵。

题意简述：

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

思路：

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

做法：

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

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

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];
		}
	}
}

公式真的没有中文标点了