CF1017F题解

这种板子题怎么能没有min25筛的题解呢？？？

题意：给定一个完全和性函数，求其前缀和。其实普通和性函数也能做就是了

\[\sum_{i=1}^n f(i) \]

类似积性函数，我们把这玩意儿在质数幂处的值之和

\[\sum_{i=1}^n \sum_{p^k|i,[\gcd(p^{k+1},i)=p^k]}kf(p) \]

\[\sum_pf(p)g(n,p) \]

其中 \(g(n,p)\) 为 \(\sum_{i=1}^n \sum_k k[p^k|i \And gcd(p^{k+1},i)=p^k]\)。

一个很明显的结论是 \(g(n,p)=n。

根号分治一下。当 \(n < p^2\) 时， \(g(n,p)=\lfloor \frac n p \rfloor\)。

于是：

\[\sum_p^{\sqrt n}f(p)g(p)+\sum_{i=\sqrt n+1}^n \lfloor \frac n i \rfloor [\text {i is prime}]f(i) \]

后者相当于对于 \([1,\sqrt n]\) 中的 \(x\) 求 \(\sum_{i=1}^{\lfloor \frac n x \rfloor}f(p)\)。因为 \(f\) 是一个多项式，所以我们相当于需要求出 \(\sum_p^{\lfloor \frac n x \rfloor} p^k\)。

时间复杂度 $O(\frac {n^{\frac 3 4} } {\log n}) $，空间复杂度 $ O(\sqrt n)$。

但是 \(n \leq 3 \times 10^8\)，而 \(\sum_{i=1}^n n^2=\frac {n(n+1)(2n+1)} 6\)，\(6\) 在模 \(2^{32}\) 的意义下没有逆元，而 \(n^3\) 破了 \(2e25\)，该怎么计算呢？

有一种办法是计算 \(3\) 在模 \(2^{32}\) 意义下的逆元，另一种办法是对 \(n\%3\) 的情况进行分类讨论。

这份代码在 CF 上面是 rk2，因为 rk1 是一个不讲武德的特判数据的人。。。

#include
#include
typedef unsigned uint;
const uint M=17325;
uint pri[2000],p1[2000],p2[2000],p3[2000],s1[2000],s2[2000],s3[2000];
uint n,S,A,B,C,D,ans,top,id1[M],id2[M],pos[M];double invp[2000];
uint g0[M<<1],g1[M<<1],g2[M<<1],g3[M<<1];
inline uint f(const uint&n,const uint&p,const double&invp){
	return n