Luogu4464 [国家集训队] JZPKIL

发表于 分类于 ， ， 阅读次数：

题意：给定 ，求

多组数据，，，，时限 。

略去 ，记 ，则 。

其中 是自然数 次方和。利用伯努利数求出自然数幂和关于求和上界的多项式 ，递推预处理复杂度 ，求一次多项式系数复杂度 。

代入可得

可以发现后面是两个积性函数 与 的卷积，是个积性函数，记为 。

使用积性分解，在 Pollard's Rho 求出 的质因数分解后，只需快速求 即可得到答案。

这里 不会很大，可以直接暴力计算。总复杂度 。