C++11(clang++ 3.9) 解法, 执行用时: 4306ms, 内存消耗: 52472K, 提交时间: 2018-10-19 19:36:44

#include<cstdio>
#include<map>
using namespace std;
#define ll unsigned long long
#define N 10000000

int p[N+5],mu[N+5];bool pri[N+5];
ll L,R;map<ll,int> f;

void pre()
{
    pri[1]=1;mu[1]=1;
    for (int i=2;i<=N;i++)
    {
        if (!pri[i]) p[++p[0]]=i,mu[i]=-1;
        for (int j=1,t;j<=p[0]&&(t=i*p[j])<=N;j++)
        {
            pri[t]=1;mu[t]=-mu[i];
            if (!(i%p[j])) {mu[t]=0;continue;}
        }
    }
    for (int i=2;i<=N;i++) mu[i]+=mu[i-1];
}

ll Sum(ll n)
{
    if (n<=N) return mu[n];
    if (f.count(n)) return f[n];ll ans=1;
    for (ll l=2,r;l<=n;l=r+1)
        r=n/(n/l),ans-=Sum(n/l)*(r-l+1);
    return f[n]=ans;
}

ll power(ll x,ll y) {
	ll ret=1;
	for (;y;y>>=1,x=x*x)
		if (y&1) ret=ret*x;
	return ret;
}

ll n,m,ans;
int main()
{
    scanf("%llu%llu",&n,&m);
	pre();
    for (ll i=1,nex;i<=m;i=nex+1) {
    	nex=m/(m/i);
    	ans+=(Sum(nex)-Sum(i-1))*power(m/i,n);
	}
	printf("%llu\n",ans);
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 3644ms, 内存消耗: 109804K, 提交时间: 2018-10-19 21:48:54

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int M=12000000;
int pri[M>>3],miu[M],Sum[M];
bool mark[M];
int pt;
ll n,m;
unordered_map<ll,int> dp;
unordered_set<ll> S;
unsigned long long Pow(unsigned long long x,long long k){
	unsigned long long res=1;
	for(;k;k>>=1,x*=x)
		if(k&1) res*=x;
	return res;
}
int calc(ll n){
	if(n<M) return Sum[n];
	if(S.count(n)) return dp[n];
	S.insert(n);
	int res=1;
	for(ll x=2,y;x<=n;x=y+1){
		y=n/(n/x);
		res-=(y-x+1)*calc(n/x);
	}
	return dp[n]=res;
}

int main(){
	miu[1]=Sum[1]=1;
	for(int i=2;i<M;i++){
		if(!mark[i]) pri[pt++]=i,miu[i]=-1;
		for(int j=0,k;j<pt && (k=i*pri[j])<M;j++){
			mark[k]=1;
			if(i%pri[j]) miu[k]=-miu[i];
			else break;
		}
		Sum[i]=Sum[i-1]+miu[i];
	}
	cin >> n >> m;
	unsigned long long res=0;
	for(ll x=1,y;x<=m;x=y+1){
		y=m/(m/x);
		res+=((unsigned long long)(calc(y)-calc(x-1)))*Pow(m/x,n);
	}
	cout << res << endl;
	return 0;
}