有毒的数学公式

题解

中d表示i的因子，即i的因子的k次方之和

不能直接快速幂求解！因为数据缘故给骗过去一个o.....orz

两个难点

1、积性函数

已知条件（优化直接快速幂）

由此用线性筛把每个数的 k 次方求解出来（直接快速幂求质数的k次方，合数的k次方利用两质数的k次方相乘得到）

2、约数和

可以发现就是从 1 到 n ，每个数约数的 k次方 和，再求和；简单来说，1~n里面存在n/i个i因子，k次方后求和即可。

CODE

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
#define ll long long
#define maxn 10000000
ll prime[maxn+7],p[maxn+7];
int vis[maxn+7];
ll n,k;
ll ksm(ll a,ll b)
{
    ll r=1,base=a;
    while(b!=0)
    {
        if(b%2)
            r=r*base%mod;
        base=base*base%mod;
        b/=2;
    }
    return r%mod;
}
void shai()
{
    p[1]=1;
    for(int i=2;i<=maxn;i++)
    {
        if(!vis[i])
        {
            prime[++prime[0]]=i;
            p[i]=ksm(i,k);
        }
        for(int j=1;j<=prime[0]&&i*prime[j]<=maxn;j++)
        {
            vis[i*prime[j]]=1;
            p[i*prime[j]]=p[i]*p[prime[j]]%mod;
            if(i%prime[j]==0)
            {
                break;
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>n>>k;
    shai();
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        ans=(ans+n/i*p[i])%mod;
    }
    cout<<ans<<endl;
    return 0;
}