前言

在看过蓝桥杯去年C++A组的翻转硬币 后有感而发

当时在考场上看到这题本来感觉就是线性筛题，但是看到数据大小感觉很震惊
$1 \le n \le 10^{18}$

那肯定就有办法呗，当时想到杜教筛了，但是没学过不会写，于是就有了这篇帖子

但是实际上根杜教筛没啥关系，其实是manacher，太菜了没做出来而已

杜教筛

先介绍下前置知识

积性函数

定义

当$f(a) * f(b) = f(a * b)$时$f(x)$就被称为积性函数

性质

1. 狄利克雷卷积：积性 * 积性 = 积性
2. $\sum_{d|n}$ 积性 = 积性

正题

杜教筛用于求积性函数的前缀和，一般可以达到$O(n^{\frac{2}{3}})$的复杂度
对于数论函数 $f$，杜教筛可以在低于线性时间的复杂度内计算 $S(n)=\sum_{i=1}^{n}f(i)$。

算法思想

我们想办法构造一个 $S(n)$ 关于 $S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)$ 的递推式。

对于任意一个数论函数 g，必满足：
\begin{aligned}
\sum_{i=1}^{n}(f * g)(i) & =\sum_{i=1}^{n}\sum_{d \mid i}g(d)f\left(\frac{i}{d}\right) =\sum_{i=1}^{n}g(i)S\left(\left\lfloor\frac{n}{i}\right\rfloor\right)
\end{aligned}
其中 $f*g$ 为数论函数 $f$ 和 $g$ 的 狄利克雷卷积。