自动搬运

查看原文

来自洛谷，原作者为

	peterwuyihong B50nErUDyjFUydNk9MUx9hIqRcwhJOvfpmZ8h2lG

搬运于2025-08-24 22:36:01，当前版本为作者最后更新于2021-10-18 12:00:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

抛砖引玉的一个题，其实是人菜，想不到别的解法

给一个原题面，我觉得我写的很好啊

题意：对于 $k=0,1,2,3,4,5,6,7$，求出：

$$\sum_{i=1}^n[\omega(i)\equiv k(\bmod 8)]3^{\omega(i)} $$

其中 $\omega(i)$ 表示 $i$ 含有几种质因子。

题解：

$n\le 100:$ 留给正宗 $O(n\sqrt n\log n)$ 做法。

$n\le 10^5:$ 留给 $O(n\log n)$ 筛法做法。

$n\le 3\times10^7:$ 留给 $O(n)$ 线性筛做法。

$n\le 10^9:$ 留给大常数和神秘做法。

$n\le 10^{10}:$ 看到取模，使用单位根反演，但是模数不一定是 $998244353$ 之类的模数，可以考虑选用一个巨大 $\text{NTT}$ 模数或者用三模 $\text{NTT}$ 原理，用 $\text{(ex)CRT}$ 大力合并。

先放一个单位根反演基本形式

$$[n|k]=\frac 1 n\sum_{i=0}^{n-1}\omega_n^{ik}$$ $$\sum_{i=1}^n[8|(\omega(i)-k)]3^{\omega(i)}=\frac1 8\sum_{i=1}^n3^{\omega(i)}\sum_{j=0}^7\omega_{8}^{j(\omega(i)-k)} $$$$=\frac 1 8\sum_{j=0}^7\omega_8^{-jk}\sum_{i=1}^n3^{\omega(i)}\omega_8^{j\omega(i)}=\frac 1 8\sum_{j=0}^7\omega_8^{-jk}\sum_{i=1}^n{(3\omega_8^j)}^{\omega(i)} $$

最后一个柿子有 $8$ 个本质不同的底数，于是做 $8$ 次 $\text{Min-25}$ 筛，然后就做完了。

来点观看比赛心路历程

我：我草，这是什么牛逼做法啊

我：好像确实可以循环卷积模拟，麻了

我：大E了大E了咋整啊我草

我：分段打表是什么玩意儿？？？？

我：寄了，只求不成为下一个yz

希望 @Silver187 和 @Remake 可以贡献他们的解法