题解：【题解】[HNOI2002] 跳蚤[莫比乌斯反演]-CSDN博客

#include<bits/stdc++.h>
using namespace std;
template<typename T> void qread(T &x){
	x=0; int f=1; char c=getchar();
	for(; !isdigit(c); c=getchar()) if(c=='-') f=-1;
	for(; isdigit(c); c=getchar()) x=x*10+(c-'0');
	x*=f;
}
typedef long long LL;
const int N=5e6+10;
const LL P=1e9+7;
int pr, prime[N];
bool v[N];
LL mu[N];
void init(){
	pr=0; memset(v, 0, sizeof(v));
	mu[0]=0; mu[1]=1;
	for(int i=2; i<=N-10; i++){
		if(!v[i]) pr++, prime[pr]=i, mu[i]=-1;
		for(int j=1; (j<=pr) && (i*prime[j]<=N-10); j++){
			int p=prime[j];
			v[i*p]=1;
			if(i%p==0){
				mu[i*p]=0;
				break;
			}
			else mu[i*p]=-mu[i];
		}
	}
	for(int i=1; i<=N-10; i++) mu[i]+=mu[i-1];
}
LL q_pow(LL a, LL b){
	LL res=1;
	while(b){
		if(b&1) res=res*a;
		a=a*a; b/=2;
	}
	return res;
}
map<LL, LL> hs;
LL calc(LL x){
	if(x<=N-10) return mu[x];
	if(hs[x]) return hs[x];
	LL res=1;
	for(LL i=2, j; i<=x; i=j+1){
		j=x/(x/i);
		res=res-calc(x/i)*(j-i+1);
	}
	return hs[x]=res;
}
LL n, m;
int main(){
	init();
	qread(n); qread(m);
	LL ans=0;
	for(LL d=1; d<=sqrt(m+1); d++) if(m%d==0){
		ans=ans+(mu[d]-mu[d-1])*q_pow(m/d, n);
		if(d*d!=m) ans=ans+(calc(m/d)-calc(m/d-1))*q_pow(d, n);
	}
	printf("%lld\n", ans);
	return 0;
}

题解：【题解】[HNOI2002] 跳蚤[莫比乌斯反演]-CSDN博客

#include<bits/stdc++.h>
using namespace std;
template<typename T> void qread(T &x){
	x=0; int f=1; char c=getchar();
	for(; !isdigit(c); c=getchar()) if(c=='-') f=-1;
	for(; isdigit(c); c=getchar()) x=x*10+(c-'0');
	x*=f;
}
typedef long long LL;
const int N=5e6+10;
const LL P=1e9+7;
int pr, prime[N];
bool v[N];
LL mu[N];
void init(){
	pr=0; memset(v, 0, sizeof(v));
	mu[0]=0; mu[1]=1;
	for(int i=2; i<=N-10; i++){
		if(!v[i]) pr++, prime[pr]=i, mu[i]=-1;
		for(int j=1; (j<=pr) && (i*prime[j]<=N-10); j++){
			int p=prime[j];
			v[i*p]=1;
			if(i%p==0){
				mu[i*p]=0;
				break;
			}
			else mu[i*p]=-mu[i];
		}
	}
	for(int i=1; i<=N-10; i++) mu[i]+=mu[i-1];
}
LL q_pow(LL a, LL b){
	LL res=1;
	while(b){
		if(b&1) res=res*a;
		a=a*a; b/=2;
	}
	return res;
}
map<LL, LL> hs;
LL calc(LL x){
	if(x<=N-10) return mu[x];
	if(hs[x]) return hs[x];
	LL res=1;
	for(LL i=2, j; i<=x; i=j+1){
		j=x/(x/i);
		res=res-calc(x/i)*(j-i+1);
	}
	return hs[x]=res;
}
LL n, m;
int main(){
	init();
	qread(n); qread(m);
	LL ans=0;
	for(LL d=1; d<=sqrt(m+1); d++) if(m%d==0){
		ans=ans+(mu[d]-mu[d-1])*q_pow(m/d, n);
		if(d*d!=m) ans=ans+(calc(m/d)-calc(m/d-1))*q_pow(d, n);
	}
	printf("%lld\n", ans);
	return 0;
}