(color{#0066ff}{ 题目描述 })
(σ_0(i)) 表示(i) 的约数个数
求(S_k(n)=sum_{i=1}^nsigma_0(i^k)mod 2^{64})
(color{#0066ff}{输入格式})
第一行一个T为数据组数
接下来每组数据一个n，一个k
(color{#0066ff}{输出格式})
每个询问输出一行
(color{#0066ff}{输入样例})
5
1 3
2 3
3 3
10 3
100 3
(color{#0066ff}{输出样例})
1
5
9
73
2302
(color{#0066ff}{数据范围与提示})
(Tleq 10^4,n,kleq10^{10})
(color{#0066ff}{ 题解 })
设p为质数
则min_25筛的使用条件就是
1、(f(p))为多项式。2、(f(p^k))容易求出。3、(f)积性函数
因为(f(p))是多项式而且是积性函数
我们考虑把(f(p))拆项，这样拆出来的就是完全积性函数
比如(varphi(p)=p-1,varphi_1(p)=p,varphi_2(p)=1)
本题(sigma(p)=2)，一个常数qwq
设拆项后(f(p)=p^k)
我们设 (egin{aligned}g(q,b)=sum_{i = 1}^q [i是质数 或 i的最小质因子>p_b]i^kend{aligned})
简单来说，(g(q,b))就是经过b轮埃氏筛法剩下的所有(in [2,q])的数的k次幂的和
如何求g呢？ 考虑递推(g(?,b-1) o g(?,b))
(g(q,b)=left{egin{aligned}g(q,b-1) q<p_b^2 \ g(q,b-1)-p_b^k*(g(lfloor frac q {p_b} floor , b-1)-g(p_{b-1},b-1)) qge p_b^2end{aligned} ight.)
若(q<p_b^2)，所有q以内的合数都已经被筛掉，不会影响
否则，考虑本轮筛掉了哪些数
每个(leq lfloorfrac q {p_b} floor)的且不含有(< p_b)的质因子的数的(p_b)倍都会在本轮筛掉
因为(g(lfloor frac q {p_b} floor , b-1))还包含了多余的质数，于是我们用其减去(g(p_{b-1},b-1)))就行了
不难发现，g数组可以滚动，而且根据递推式，第二维完全可以不要
初始g(a,0)=a-1（不算1）
因为我们的操作都跟质数有关，打表可以发现，数列分块的r有一些规律
当(g[r_i] e g[r_{i-1}])时，说明(r_i)是质数
显然这样数组是开不下的，我们让g用r的数组下标，这样空间复杂度就是(sqrt n)
设(|p|)素数集合大小，(egin{aligned}S(a,b)=sum_{i=2}^a [i的最小质因子ge p_b]f(i)end{aligned})
设(S(a,b)=left{egin{aligned}0 aleq p_b \ g(a,|p|)-g(p_{b-1},|p|)+sum_{i=b}^{|p|}sum_{p_i^{t+1}leq a}(S(frac a {p_i^t} ,i+1)*f(p_i^t)+f(p_i^{t+ 1})) qge p_b^2end{aligned} ight.)
递归求解即可
#include<bits/stdc++.h>
#define LL long long
LL in() {
char ch; LL x = 0, f = 1;
while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));
return x * f;
}
const int maxn = 3e6 + 10;
LL n, k, sqt;
LL a[maxn], g[maxn];
int m, tot, pri[maxn];
int getid(LL x) { return x <= sqt? x : m - n / x + 1; }
unsigned LL getans(LL a, int b) {
if(a < pri[b]) return 0;
unsigned LL ans = (k + 1) * (g[getid(a)] - g[getid(pri[b - 1])]);
for(int i = b; i <= tot && (LL)pri[i] * pri[i] <= a; i++)
for(LL x = pri[i], f = k + 1; x * pri[i] <= a; x *= pri[i], f += k)
ans += (getans(a / x, i + 1) * f + f + k);
return ans;
}
int main() {
for(int T = in(); T --> 0;) {
n = in(), k = in();
sqt = sqrt(n);
tot = m = 0;
for(LL i = 1; i <= n; i = a[m] + 1)
a[++m] = n / (n / i), g[m] = a[m] - 1;
for(int i = 2; i <= sqt; i++)
if(g[i] != g[i - 1]) {
pri[++tot] = i;
LL s = (LL)i * i;
for(int j = m; a[j] >= s; j--)
g[j] -= g[getid(a[j] / i)] - g[i - 1];
}
printf("%llu
", getans(n, 1) + 1);
}
return 0;
}