40分超时

#include<bits/stdc++.h>
#define LL long long
using namespace std;
constexpr int N=1e7+10;
int n,k;
LL p[N],s[N];
bool v[N];
inline LL qpow(LL a,LL b)
{
    LL res=1;
    for(;b;b>>=1,a=1ll*a*a%1000000007)if(b&1) res=1ll*res*a%1000000007;
    return res;
}
int main()
{
    scanf("%d%d",&n,&k);
  
    LL ans=0;
    for(int i=1;i<=n;i++) 
		for(int d=1;d<=i;d++)if(i%d==0)
			ans=(ans+qpow(d,k))%1000000007;
    printf("%lld\n",ans);
    return 0;
}

80分超时

#include<bits/stdc++.h>
#define LL long long
using namespace std;
constexpr int N=1e7+10;
int n,k;
LL p[N],s[N];
bool v[N];
inline LL qpow(LL a,LL b)
{
    LL res=1;
    for(;b;b>>=1,a=1ll*a*a%1000000007)if(b&1) res=1ll*res*a%1000000007;
    return res;
}
int main()
{
    scanf("%d%d",&n,&k);
    LL ans=0;
    for(int i=1;i<=n;i++) ans=(ans+qpow(i,k)*(n/i))%1000000007;
    printf("%lld\n",ans);
    return 0;
}

标程

#include<bits/stdc++.h>
#define LL long long
using namespace std;
constexpr int N=1e7+10,mod=1e9+7;
int n,k,pr;
LL p[N],s[N];
bool v[N];
inline LL qpow(LL a,LL b)
{
    LL res=1;
    for(;b;b>>=1,a=1ll*a*a%mod)if(b&1) res=1ll*res*a%mod;
    return res;
}
int main()
{
    scanf("%d%d",&n,&k);
    pr=0;memset(v,0,sizeof(v));v[1]=1;
    s[1]=1;
    for(int i=2;i<=n;i++)
	{
        if(!v[i]) p[++pr]=i,s[i]=qpow(i,k);
        for(int j=1;j<=pr&&i*p[j]<=n;j++)
		{
            v[i*p[j]]=1;
            s[i*p[j]]=1ll*s[i]*s[p[j]]%mod;
            if(i%p[j]==0)break;
        }
    }
    LL ans=0;
    for(int i=1;i<=n;i++) ans=(ans+s[i]*(n/i))%mod;
    printf("%lld\n",ans);
    return 0;
}