意义不明的题解

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e7;
LL mod;
int pr,p[N+10];LL mu[N+10];bool v[N+10];
void init()
{
	memset(v,0,sizeof(v));
	pr=0;mu[0]=0;mu[1]=1;
	for(int i=2;i<=N;i++)
	{
		if(!v[i])p[++pr]=i,mu[i]=-1;
		for(int j=1;j<=pr&&i*p[j]<=N;j++)
		{
			v[i*p[j]]=1;
			if(i%p[j]==0){mu[i*p[j]]=0;break;}
			mu[i*p[j]]=-mu[i];
		}
	}
	for(int i=1;i<=N;i++)mu[i]+=mu[i-1];
}
LL chen(LL a,LL b)//相当于乘法,为了防止爆long long 
{
	LL res=0;a%=mod;b%=mod;
	for(;b;b>>=1,a=(a+a)%mod)if(b&1)res=(res+a)%mod;
	return res;
}
LL qpow(LL a,LL b)
{
	LL res=1;a%=mod;
	for(;b;b>>=1,a=chen(a,a))if(b&1)res=chen(res,a);
	return res;
}
int main()
{
	init();
	LL n,m;scanf("%lld%lld%lld",&n,&m,&mod);
	LL ans=0;
	for(int l=1,r;l<=m;l=r+1)//每一维的上限都相等，也就是a1=a2=a3……，所以可以去掉min，用qpow
	{
		r=m/(m/l);//相当于P1282的min({a/(a/l), b/(b/l),c/(c/l)}),因为a1=a2=a3……所以可以去掉 
		ans=(ans+chen((mu[r]-mu[l-1]+mod)%mod,qpow(m/l,n/*n维*/)))%mod;
	}
	printf("%lld\n",ans);
	return 0;
}

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e7;
LL mod;
int pr, p[N+10];LL mu[N+10]; bool v[N+10];
void init()
{
	memset(v,0,sizeof(v));
	pr=0;mu[0]=0;mu[1]=1;
    for(int i=2;i<=N;i++)
	{
        if(!v[i]) p[++pr]=i, mu[i]=-1; 
        for(int j=1;j<=pr&&p[j]*i<=N;j++)
		{
            v[i*p[j]]=true;
            if(i%p[j]==0){mu[i*p[j]]=0;break;}
            mu[i*p[j]]=-mu[i];
        }
    }
    for(int i=1;i<=N;i++) mu[i]+=mu[i-1];
}
LL chen(LL a,LL b)
{
	LL res=0;a%=mod;b%=mod;
	for(;b;b>>=1,a=(a+a)%mod)if(b&1)res=(res+a)%mod;
	return res;
}
LL qpow(LL a,LL b)
{
	LL res=1;a%=mod;
	for(;b;b>>=1,a=chen(a,a))if(b&1)res=chen(res,a);
	return res;
}
int main()
{
	init();
	LL n,m;scanf("%lld%lld%lld",&n,&m,&mod);
	LL ans=0;
    for(int l=1,r;l<=m;l=r+1)
	{
        r=m/(m/l);
        ans=(ans+chen((mu[r]-mu[l-1]+mod)%mod, qpow(m/l, n)) )%mod;
    }
    printf("%lld\n",ans);
    return 0;
}