神仙数论。
真难写……
随手推一下,原式变为 n∑x=1k∑d=1fd(x)(2⌊nx⌋∑i=1φ(i)−1)。
对 φ 杜教筛,然后考虑设 Fd(n)=n∑i=1fd(i)。
考虑容斥,可以强行钦定几个质因子的指数大于 d,然后删去贡献(f∞),然后再把重复算的贡献补回。
即 Fd(n)=n∑i=1fd(i)=n∑i=1μ(i)⌊nid+1⌋∑j=1f∞(id+1j)=n∑i=1fd+1∞(i)μ(i)F∞(⌊nid+1⌋)=⌊n1/(d+1)⌋∑i=1fd+1∞(i)μ(i)F∞(⌊nid+1⌋)
这是因为 f∞ 是完全积性函数。
于是如果能求得 F∞,Fd 就可以在 O(n2/3k2/3) 内求得,即预处理 + 暴力算(实际上由于空间问题达不到这个最优值)。
考虑杜教筛,注意到若 n=m∏i=1pcii,则 (f∞∗1)(n)=m∏i=1[2|ci],即 n 为完全平方数。
于是就做完了。
(当然直接 Min_25 筛或者洲阁筛也不错)
但是有一点,即 Fd 的预处理。
实际上是可以直接把 k∑d=1fd(n) 的前缀和线性筛出来的。
具体的说,由于每个 fd 的贡献非 0 即 f∞,故只需要筛出每个数的质因子最大指数,然后算出有多少个 d 使得 fd 有贡献,乘上 f∞ 的值即可。
上文中有提到求 k∑d=1fd 的复杂度,注意到若预处理 (nk)2/3=n2/3k2/3 内的值,可以达到最优复杂度 O(n2/3k2/3),但是由于空间问题无法达到。
所以就大概少预处理个 2×107 的样子吧(逃
代码(杜教筛):
1 |
|
代码(Min_25 筛):
1 |
|