#P15528. [HNOI2026省队集训]Sum

    ID: 14740 传统题 文件IO:sum 3000ms 1024MiB 尝试: 28 已通过: 3 难度: 9 上传者: 标签>CF2600数论莫比乌斯反演筛法组合数学数学算法基础前缀和

[HNOI2026省队集训]Sum

Sum

给定非负整数 n,kn,k 与序列 a1,a2,…,ama_1,a_2,\dots,a_m (其中 m=⌊n⌋m = \lfloor \sqrt n \rfloor )

试求以下表达式对 998244353998244353 取模的值:

∑i=1nav(i)ik\sum_{i=1}^na_{v(i)}i^k

其中 v(i)v(i) 表示 ii 最大的平方因子,即 v(i)=max⁡{j∣j∈N∗,j2∣i}v(i) = \max\{j|j \in \N^*,j^2 | i\}。

输入格式

第一行输入两个数 n,kn,k。

第二行输入 m=⌊n⌋m = \lfloor \sqrt n \rfloor 个数 a1,a2,…,ama_1,a_2,\dots,a_m。

输出格式

一行一个数,表示答案。

样例输入 1

2 1
3

[Copy](javascript:;)

样例输出 1

9

[Copy](javascript:;)

样例解释 1

对 i=1,v(i)=1,av(i)=3,av(i)ik=3i = 1,v(i) = 1,a_{v(i)} = 3,a_{v(i)}i^k=3

对 i=2,v(i)=1,av(i)=3,av(i)ik=6i = 2,v(i) = 1,a_{v(i)} = 3,a_{v(i)}i^k = 6

所以 ∑i=1nav(i)ik=9\sum_{i=1}^n a_{v(i)}i^k = 9

样例输入 2

10 5
3 7 6

[Copy](javascript:;)

样例输出 2

974790

[Copy](javascript:;)

样例解释 2

v(1)∼v(10)v(1) \sim v(10) 分别为 1,1,1,2,1,1,1,2,3,11,1,1,2,1,1,1,2,3,1 ,代入原式可得结果为 974790974790。

样例输入 3 / 样例输出 3

见 down/sum_sample3.in 和 down/sum_sample3.out。该样例满足测试点 1∼41 \sim 4 的限制。

样例输入 4 / 样例输出 4

见 down/sum_sample4.in 和 down/sum_sample4.out。该样例满足测试点 5∼65 \sim 6 的限制。

样例输入 5 / 样例输出 5

见 down/sum_sample5.in 和 down/sum_sample5.out。该样例满足测试点 11∼1211 \sim 12 的限制。

样例输入 6 / 样例输出 6

见 down/sum_sample6.in 和 down/sum_sample6.out。该样例满足测试点 13∼1413 \sim 14 的限制。

样例输入 7 / 样例输出 7

见 down/sum_sample7.in 和 down/sum_sample7.out。该样例满足测试点 15∼2015 \sim 20 的限制。

数据范围

测试点编号 n≤n \le k≤k \le 特殊限制
1∼41 \sim 4 10610^6 10910^9
5∼65 \sim 6 101110^{11} 22
7∼87 \sim 8 20002000
9∼109 \sim 10 5×1045 \times 10^4
11∼1211 \sim 12 10610^6 A
13∼1413 \sim 14 B
15∼2015 \sim 20

特殊限制 A:对所有 $1 \le i \le \dfrac{\lfloor \sqrt n \rfloor}{3},a_i = 0$

特殊限制 B:对所有 i≥2,ai=0i \ge 2,a_i = 0

所有数据满足:$1 \le n \le 10^{11},0 \le k \le 10^6,0 \le a_i < 998244353$