HDU6537 [CCPC2019 湘潭邀请赛] Neko and function

Description

f(n,k)=a1=2na2=2nak=2n[i=1kai=n]f\left(n,k\right)=\sum_{a_1=2}^n\sum_{a_2=2}^n\dots\sum_{a_k=2}^n\left[\prod_{i=1}^ka_i=n\right]

给定 n,kn,k (1n230, 1k30)\left(1\leq n\leq2^{30},\ 1\leq k\leq30\right) ,求

ans=(i=1nf(i,k))mod(109+7)ans=\left(\sum\limits_{i=1}^nf\left(i,k\right)\right)\bmod\left(10^9+7\right)

HDU 上为多组测试。


Solution

设唯一分解后 n=i=1mpiein=\prod\limits_{i=1}^mp_i^{e_i} ,则有

g(n,k)=a1=1na2=1nak=1n[i=1kai=n]=i=1m(ei+k1k1)g\left(n,k\right)=\sum_{a_1=1}^n\sum_{a_2=1}^n\dots\sum_{a_k=1}^n\left[\prod_{i=1}^ka_i=n\right]=\prod_{i=1}^m\binom{e_i+k-1}{k-1}

容斥原理

f(n,k)=i=0k(1)i(ki)g(n,ki)f\left(n,k\right)=\sum_{i=0}^k\left(-1\right)^i\binom kig\left(n,k-i\right)

ans=i=1nf(i,k)=i=1nj=0k(1)j(kj)g(i,kj)=j=0k(1)j(kj)i=1ng(i,kj)\begin{aligned} ans&=\sum\limits_{i=1}^nf\left(i,k\right)\\ &=\sum_{i=1}^n\sum_{j=0}^k\left(-1\right)^j\binom kjg\left(i,k-j\right)\\ &=\sum_{j=0}^k\left(-1\right)^j\binom kj\sum_{i=1}^ng\left(i,k-j\right) \end{aligned}

S(n,k)=i=1ng(i,k)S\left(n,k\right)=\sum\limits_{i=1}^ng\left(i,k\right) ,则

ans=i=0k(1)i(ki)S(n,ki)ans=\sum_{i=0}^k\left(-1\right)^i\binom kiS\left(n,k-i\right)

固定 kk ,考虑如何求 S(n,k)S\left(n,k\right) .
显然 g(n,k)g\left(n,k\right) 是关于 nn积性函数 ,设 pprimep\in prime ,则 g(p,k)=kg\left(p,k\right)=k .
考虑 Min_25 筛 ,记 fk(n)=k=kf1(n)f_k\left(n\right)=k=k\cdot f_1\left(n\right) .
显然

Fprimek(n)=2pnfk(p)=k2pnf1(p)=kFprime1(n)F^k_{prime}\left(n\right)=\sum_{2\leq p\leq n}f_k\left(p\right)=k\sum_{2\leq p\leq n}f_1\left(p\right)=k\cdot F^1_{prime}\left(n\right)

故只需预处理 Fprime1F^1_{prime} ,之后令 Fprime(n)=kFprime1(n)F_{prime}\left(n\right)=k\cdot F^1_{prime}\left(n\right)Min_25 筛即可。

时间复杂度:O(n34logn)\mathcal O\left(\sum\frac{n^{\frac34}}{\log n}\right) .


Code

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
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;
#define idx(x) ((x) <= sq ? le[(x)] : ge[n / (x)])

const int N = (1 << 15) + 5;
const int M = 1e2 + 5;
const int p = 1e9 + 7;
int n, k;
int ct, pri[N], c[M][M];
bool isp[N];
int pc, le[N], ge[N], pt[N << 1];
int sq, ans, g[N << 1];

void init(void);
void solve(void);
void min_25_g(void);
int min_25_f(int x, int y, int k);
int add(int a, int b);
int sub(int a, int b);
int mul(int a, int b);

int main(void) {
init();
while (~scanf("%d%d", &n, &k)) solve();
return 0;
}

void init(void) {
for (int i = 0; i < M; i++) c[i][0] = 1;
for (int i = 1; i < M; i++)
for (int j = 1; j <= i; j++)
c[i][j] = add(c[i - 1][j], c[i - 1][j - 1]);
memset(isp, true, sizeof(isp)), isp[0] = isp[1] = false;
for (int i = 2; i < N; i++) {
if (isp[i]) pri[++ct] = i;
for (int j = 1; j <= ct && i * pri[j] < N; j++) {
isp[i * pri[j]] = false;
if (!(i % pri[j])) break;
}
}
}

void solve(void) {
min_25_g(), ans = 0;
for (int i = 0, f = 1; i <= k; i++, f = f == 1 ? p - 1 : 1)
ans = add(ans, mul(mul(f, c[k][i]), add(min_25_f(n, 1, k - i), 1)));
printf("%d\n", ans);
}

void min_25_g(void) {
sq = sqrt(n), pc = 0;
for (int i = 1, j; i <= n; i = n / j + 1)
pt[++pc] = j = n / i, idx(j) = pc, g[pc] = j - 1;
for (int i = 1; i <= ct; i++)
for (int j = 1; j <= pc && pri[i] <= pt[j] / pri[i]; j++)
g[j] = sub(g[j], sub(g[idx(pt[j] / pri[i])], i - 1));
}

int min_25_f(int x, int y, int k) {
if (x <= 1 || x < pri[y]) return 0;
int r = mul(k, sub(g[idx(x)], y - 1));
for (int i = y; i <= ct && pri[i] <= x / pri[i]; i++)
for (int e = 1, pe = pri[i]; pe <= x / pri[i]; e++, pe *= pri[i]) {
r = add(r, mul(c[e + k - 1][k - 1], min_25_f(x / pe, i + 1, k)));
r = add(r, c[e + k][k - 1]);
}
return r;
}

inline int add(int a, int b) { return (a += b) < p ? a : a - p; }

inline int sub(int a, int b) { return (a -= b) < 0 ? a + p : a; }

inline int mul(int a, int b) { return a * 1ll * b % p; }

Tsukkomi

训练时怼了一个小时没搞明白 QAQ

Welcome to my other publishing channels