链接：https://loj.ac/problem/124

 

就是筛一下积性函数。

 

#include
     
      #define ll long long#define maxn 10000000#define ha 1000000007using namespace std;int zs[maxn/10],t=0;int low[maxn+5];int f[maxn+5];int mik[maxn+5];bool v[maxn+5];int n,k;inline int ksm(int x,int y){	int an=1;	for(;y;y>>=1,x=x*(ll)x%ha) if(y&1) an=an*(ll)x%ha;	return an;}inline int add(int x,int y){	x+=y;	return x>=ha?x-ha:x; }inline void init(){	low[1]=1,f[1]=1;		for(int i=2;i<=n;i++){		if(!v[i]) zs[++t]=i,low[i]=i,mik[i]=ksm(i,k),f[i]=add(mik[i],1);		for(int j=1,u;j<=t&&(u=zs[j]*i)<=n;j++){			v[u]=1;			if(!(i%zs[j])){				low[u]=low[i]*zs[j];				if(low[i]==i) f[u]=add(f[i]*(ll)mik[zs[j]]%ha,1);				else f[u]=f[i/low[i]]*(ll)f[low[u]]%ha;				break;			}			low[u]=zs[j],f[u]=f[i]*(ll)(mik[zs[j]]+1)%ha;		}	}		for(int i=1;i<=n;i++) f[i]=add(f[i],f[i-1]);}int main(){	cin>>n>>k;	init();	cout<
      
       <