有毒的玻璃球

题解：
可以发现就是从 1 到 n ，每个数约数的 k次方 和，再求和；
由此用线性筛把每个数的 k 次方求解出来，然后用约数和的计算方法求解

标程：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e7+7,mod = 1e9+7;
int prime[N],f[N],cnt;
bool vis[N];
long long qpow(int x,int p){
    long long ans = 1,tmp = x;
    while(p>0){
        if(p&1)ans = (ans*tmp)%mod;
        tmp = (tmp*tmp)%mod;
        p>>=1;
    }
    return ans;
}
void xxs(int n,int k){//线性筛求解每个数的 k 次方
    f[1] = 1;
    for(int i=2;i<=n;i++){
        if(!vis[i]){
            vis[i] = 1;
            prime[cnt++] = i;
            f[i] = qpow(i,k);
        }
        for(int j=0;j<cnt&&1ll*prime[j]*i<=n;j++){
            f[prime[j]*i] = (1ll*f[prime[j]]*f[i])%mod;
            vis[prime[j]*i] = 1;
            if(i%prime[j]==0)break;
        }
    }
}
int main(){
    int n,k;
    scanf("%d %d",&n,&k);
    xxs(n,k);
    long long ans = 0;
    for(int i=1;i<=n;i++)ans = (ans+1ll*(n/i)*f[i]%mod)%mod;//约数和
    printf("%lld\n",ans);
}