P8104 「LCOI2021」 Cow Function 记录

· · 题解

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

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

题意：对于 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 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 可以贡献他们的解法