考虑函数 \(f(x) = \sigma_0(x^k)\) 在质数和质数次幂处的值。
考虑 \(f(p)\)，容易发现 \(f(p) = \sigma_0(p^k) = k + 1\)。
考虑 \(f(p^c)\)，容易发现 \(f(p^c) = \sigma_0((p^c)^k) = \sigma_0(p^{ck}) = ck + 1\)。
其中 \(p\) 为任意质数。
于是直接套用模板即可。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
using namespace std;
const long long N = 1e10;
const int MX = 1e5;
int T;
unsigned long long n,K;
int lim;
int vis[MX + 5],cnt,prime[MX + 5];
int tot,le[MX + 5],ge[MX + 5];
inline int &id(long long x)
{
return x <= lim ? le[x] : ge[n / x];
}
unsigned long long lis[2 * MX + 5];
unsigned long long G[2 * MX + 5],Fprime[2 * MX + 5];
unsigned long long F(int k,unsigned long long n)
{
if(n < (unsigned long long)prime[k] || n <= 1)
return 0;
unsigned long long ret = Fprime[id(n)] - (k - 1) * (K + 1);
for(register int i = k;i <= cnt && (unsigned long long)prime[i] * prime[i] <= n;++i)
{
unsigned long long pw = prime[i],pw2 = (unsigned long long)prime[i] * prime[i];
for(register int c = 1;pw2 <= n;++c,pw = pw2,pw2 *= prime[i])
ret += (c * K + 1) * F(i + 1,n / pw) + ((c + 1) * K + 1);
}
return ret;
}
int main()
{
for(register int i = 2;i <= MX;++i)
{
if(!vis[i])
prime[++cnt] = i;
for(register int j = 1;j <= cnt && i * prime[j] <= MX;++j)
{
vis[i * prime[j]] = 1;
if(!(i % prime[j]))
break;
}
}
scanf("%d",&T);
for(;T;--T)
{
scanf("%llu%llu",&n,&K),lim = sqrt(n),tot = 0;
for(unsigned long long l = 1,r;l <= n;l = r + 1)
{
r = n / (n / l);
lis[id(n / l) = ++tot] = n / l;
G[tot] = n / l - 1;
}
for(register int k = 1;k <= cnt;++k)
{
int p = prime[k];
unsigned long long s = (unsigned long long)p * p;
for(register int i = 1;lis[i] >= s && i <= tot;++i)
G[i] -= G[id(lis[i] / p)] - (k - 1);
}
for(register int i = 1;i <= tot;++i)
Fprime[i] = (K + 1) * G[i];
printf("%llu\n",F(1,n) + 1);
}
}