CF1017F The Neutral Zone

注意：本题的内存限制不同寻常！ 战争结束后，中立区被毁坏的城市得到了重建，孩子们也重返校园。 战争改变了世界，也改变了教育。在那些艰难的日子里，诞生了一个新的数学概念。 众所周知，对数函数可以表示为： $$ \log(p_1^{a_1}p_2^{a_2}\ldots p_k^{a_k}) = a_1 \log p_1 + a_2 \log p_2 + \ldots + a_k \log p_k $$ 其中 $p_1^{a_1}p_2^{a_2}\ldots p_k^{a_k}$ 是一个整数的质因数分解。问题在于，这个函数在定义中用到了自身，这也是它难以计算的原因。 因此，中立区的数学家们发明了这样一个概念： $$ \text{exlog}_f(p_1^{a_1}p_2^{a_2}\ldots p_k^{a_k}) = a_1 f(p_1) + a_2 f(p_2) + \ldots + a_k f(p_k) $$ 注意，$\text{exlog}_f(1)$ 总是等于 $0$。 对于任意函数 $f$，这个概念对孩子们来说太难了。因此老师告诉他们，在日常使用中，$f$ 只能是次数不超过 $3$ 的多项式（即 $f(x) = Ax^3 + Bx^2 + Cx + D$）。 “下课了！别忘了做作业！”作业如下： $$ \sum_{i=1}^n \text{exlog}_f(i) $$ 请帮助孩子们完成作业。由于答案可能非常大，你需要输出答案对 $2^{32}$ 取模的结果。

一行包含五个整数 $n$、$A$、$B$、$C$、$D$，满足 $1 \leq n \leq 3 \times 10^8$，$0 \leq A,B,C,D \leq 10^6$。

输出答案对 $2^{32}$ 取模后的结果。

在第一个样例中： $\text{exlog}_f(1) = 0$ $\text{exlog}_f(2) = 2$ $\text{exlog}_f(3) = 3$ $\text{exlog}_f(4) = 2 + 2 = 4$ $\text{exlog}_f(5) = 5$ $\text{exlog}_f(6) = 2 + 3 = 5$ $\text{exlog}_f(7) = 7$ $\text{exlog}_f(8) = 2 + 2 + 2 = 6$ $\text{exlog}_f(9) = 3 + 3 = 6$ $\text{exlog}_f(10) = 2 + 5 = 7$ $\text{exlog}_f(11) = 11$ $\text{exlog}_f(12) = 2 + 2 + 3 = 7$ $\sum_{i=1}^{12} \text{exlog}_f(i) = 63$ 在第二个样例中： $\text{exlog}_f(1) = 0$ $\text{exlog}_f(2) = (1 \times 2^3 + 2 \times 2^2 + 3 \times 2 + 4) = 26$ $\text{exlog}_f(3) = (1 \times 3^3 + 2 \times 3^2 + 3 \times 3 + 4) = 58$ $\text{exlog}_f(4) = 2 \times \text{exlog}_f(2) = 52$ $\sum_{i=1}^4 \text{exlog}_f(i) = 0 + 26 + 58 + 52 = 136$ 由 ChatGPT 4.1 翻译