除数函数求和
2huk
·
·
个人记录
除数函数求和
Description
除数函数定义为 \sigma_k(n) = \sum_{d \mid n} d^k，求 \sum_{i = 1}^n \sigma_k(i) \mod 1000000007。
## Solution
不妨计算每个数对答案的贡献。具体的，对于 $x$，那么 $x$ 的倍数都会在计算除数函数时计算到 $x$，那么我们可以求出 $x$ 实际的贡献（$x^k$）和 $x$ 贡献的次数（也就是 $x$ 的倍数个数 $\lfloor \frac nx \rfloor$）。所以第 $x$ 个数对答案的贡献即 $x^k \times \left \lfloor \dfrac nx \right \rfloor$。
直接快速幂计算 $x^k$ 是会超时的，所以考虑预处理求出所有 $x \in [1, n]$ 的 $x^k$ 的值。
可以注意到，若将 $x$ 质因数分解为 $\alpha_1^{\beta_1}\alpha_2^{\beta_2}\cdots\alpha_t^{\beta_t}$（其中 $\alpha_1, \alpha_2, \dots. \alpha_t$ 为质数），那么很显然有：
$$
x^k = \left(\alpha_1^{\beta_1}\right)^k\left(\alpha_2^{\beta_2}\right)^k\cdots \left(\alpha_t^{\beta_t}\right)^k
$$
首此启发，我们可以暴力（指复杂度为 $\log n$ 的快速幂）求出每个质数的 $k$ 次方的值，然后将每个数的质因子的答案相乘即可。
显然这一步可以在欧拉筛的过程中计算。定义 $v_i = i^k$。枚举时，若 $i$ 为质数，则直接快速幂计算 $v_i$。否则枚举质数 $p_j$，那么 $v_{p_j \cdot i}$ 的显然为 $v_{p_j}\cdot v_i$。然后就能预处理出所有 $x \in [1, n]$ 的 $x^k$ 的值了。
## Code
~~~cpp
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e7 + 10, P = 1e9 + 7;
int n, k, res;
int p[N], v[N], cnt;
bool st[N];
int fpm(int a, int b)
{
int res = 1;
while (b)
{
if (b & 1) res = (LL)res * a % P;
b >>= 1, a = (LL)a * a % P;
}
return res;
}
int main()
{
cin >> n >> k;
v[1] = 1;
for (int i = 2; i <= n; ++ i )
{
if (!st[i]) p[ ++ cnt] = i, v[i] = fpm(i, k);
for (int j = 1; p[j] <= n / i; ++ j )
{
st[p[j] * i] = true;
v[p[j] * i] = (LL)v[p[j]] * v[i] % P;
if (i % p[j] == 0) break;
}
}
for (int i = 1; i <= n; ++ i )
res = (res + (LL)n / i * v[i]) % P;
cout << res;
return 0;
}
~~~