2019徐州网络赛 H.funtion

$i=p_1^{m_1}p_2^{m_2}…p_k^{m_k}$,$f(i)=m_1+m_2..m_k$

$f(ab)=f(a)+f(b)$

考虑每个$p_i^k$作出的贡献,比如$2$作出贡献为$(n-2+1)+(n-4+1)..(n-\frac{n}{2}\times 2+1)$,等差数列求和即可,并且$4$的贡献与$2$互相独立。

$e\leq2$暴力即可

$e=1$

只需要知道每块的质数$\sum_i (1-i)$即可,正好块在$Min25$中正好求过。就结束了。不卡常好心出题人啊!

代码
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <bits/stdc++.h>
#include <time.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 1e6 + 10;
const int mod = 998244353;

int pcnt, pr[N], npr[N];
int inc(int x, int y) { return (x + y >= mod) ? (x + y - mod) : (x + y); }
int del(int x, int y) { return (x - y < 0) ? (x - y + mod) : (x - y); }
int qpow(int a, int x, int mo)
{
int res = 1;
while (x)
{
if (x & 1)
res = 1ll * res * a % mo;
a = 1ll * a * a % mo;
x >>= 1;
}
return res;
}
void Prime_init(int X)
{
npr[1] = 1;
for (int i = 1; i <= X; i++)
{
if (!npr[i])
{
pr[++pcnt] = i;
}
for (int j = 1; j <= pcnt && pr[j] * i <= X; j++)
{
npr[pr[j] * i] = 1;
if (i % pr[j] == 0)
{
break;
}
}
}
}
int sp0[N], sp1[N];

int cnt = 0;
ll p[N];
int g0[N], g1[N];
int pos1[N], pos2[N];
ll Lim;
ll n;

int main()
{
scanf("%lld", &n);
int Inv2 = qpow(2, mod - 2, mod);
//int Inv6 = qpow(6, mod - 2, mod);
Lim = sqrt(n);
Prime_init(Lim);

for (int i = 1; i <= pcnt; i++)
sp0[i] = (sp0[i - 1] + 1) % mod, sp1[i] = (sp1[i - 1] + pr[i]) % mod;
for (ll i = 1, j; i <= n; i = j + 1)
{
j = n / (n / i);
ll k = n / i;
p[++cnt] = k;
if (k <= Lim)
pos1[k] = cnt;
else
pos2[n / k] = cnt;
k %= mod;
g0[cnt] = k - 1;
g1[cnt] = 1ll * k * (k + 1) % mod * Inv2 % mod;
g1[cnt] = del(g1[cnt], 1);
}
for (int i = 1; i <= pcnt; i++)
{
for (int j = 1; j <= cnt && 1ll * pr[i] * pr[i] <= p[j]; j++)
{
int k = (p[j] / pr[i] <= Lim) ? pos1[p[j] / pr[i]] : pos2[n / (p[j] / pr[i])];
g0[j] = del(g0[j], del(g0[k], sp0[i - 1]));
g1[j] = del(g1[j], 1ll * pr[i] * del(g1[k], sp1[i - 1]) % mod);
}
}
int ans = 0;
for (int i = 1; i <= pcnt; i++)
{
ll pe = 1ll * pr[i] * pr[i];
for (int e = 2; pe <= n; e++, pe = pe * pr[i])
{
ll d = n / pe;

ll x = del(2 * (n + 1) % mod, pe % mod * (d % mod + 1) % mod);
ans = inc(ans, d % mod * x % mod * Inv2 % mod);
}
}

for (int i = 1; i <= cnt; i++)
{
ll num = del(g0[i], g0[i + 1]);
ll sum = del(g1[i], g1[i + 1]);

ll d = n / p[i];

ll x = del(2 * (n % mod + 1) % mod * num % mod, sum * (d % mod + 1) % mod);
ans = inc(ans, d % mod * x % mod * Inv2 % mod);
}

cout << ans << endl;
}