Caliwa 的博客

博客

Completely Multiplicative Function 题解

2019-11-01 07:29:48 By Caliwa

由于f是完全积性函数,因此f(1)=1,并且只需要确定所有质数的函数值。

对于质数x,若x mod 3 = 1,取f(x)=1,否则取f(x)=-1。

设s表示f的前缀和,那么s(x)=-s(x/3)+(0或1)

因此|s(x)|<= $\left\lceil \log_3x/2\right\rceil$

评论

No comments yet.

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。

可以用/kel来使用表情 kel。