LOJ #124. 除数函数求和 1

题目描述

$\sigma_k(n) = \sum_{d | n} d ^ k$

求 $\sum_{i=1}^n\sigma_k(i)$ 的值对 10⁹ 取模的结果。

输入格式

第一行两个正整数 n,k 。

输出格式

第一行输出答案。

样例

输入样例

5 2

输出样例

数据范围与提示

对于 100% 的数据，1≤n,k≤10⁷7 。

Solution：

　　本题ZYYS。。。

　　直接枚举显然不行，我们考虑改为求$n$的某一因子$d$在整个函数中的贡献是多少。

　　套上数论分块的思想，一个因子$d$对式子的贡献是$\lfloor{\frac{n}{d}}\rfloor\times d^k$。

　　这样我们需要处理的就是$d^k$，直接$O(n\log k)$快速幂求出每个因子的幂是肯定不行的，因为$n$是$10^7$，直接会T。

　　那么还是考虑优化，我们发现，每个数都能唯一分解，而在求幂时会有重复计算的质因子幂。于是，我们考虑线筛，这样就可以用每个数的最小质因子幂去算它的幂了，那么整个过程只会对$n\leq 10^7$内的质数进行快速幂，最后复杂度就成了$\sqrt n \log k$，完全可行。

　　所以最后就只需再$O(n)$扫一遍因子累加贡献求和就好了。

代码：

#include<iostream>

#define il inline

#define ll long long

#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)

#define Bor(i,a,b) for(int (i)=(b);(i)>=(a);(i)--)

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)>(b)?(b):(a))

using namespace std;

const int N=1e7,mod=1e9+;

int prime[N+],ans,cnt,n,k,sum[N+];

bool isprime[N+];

il int fast(ll s,ll k){

    ll ans=;

    while(k){

        if(k&)ans=ans*s%mod;

        k>>=;

        s=s*s%mod;

    }

    return ans;

}

il void init(){

    sum[]=;

    For(i,,n+) {

        if(!isprime[i]) prime[++cnt]=i,sum[i]=fast(i,k);

        for(int j=;j<=cnt&&prime[j]*i<=n+;j++){

            isprime[prime[j]*i]=;

            sum[prime[j]*i]=sum[i]*1ll*sum[prime[j]]%mod;

            if(i%prime[j]==)break;

        }

    }

}

int main(){

    ios::sync_with_stdio();

    cin>>n>>k;

    init();

    For(i,,n) ans=(ans+1ll*(n/i)*sum[i])%mod;

    cout<<ans;

    return ;

}

秒客网