一个人的数论 湖北省队互测2014

[湖北省队互测2014] 一个人的数论

我必须承认我现在一点注意力都没有

题目链接： [湖北省队互测2014] 一个人的数论 。

题目描述：

给定 $n$ 的质因数分解方式 $\prod\limits_{i=1}^w p_i^{a_i}$ ，求：

$$(\sum_{i=1}^n i^k[i\perp n])\bmod (10^9+7)$$

保证 $1\le w \le 10^3$ ， $2 \le p_i,a_i \le 10^9$ ， $1\le k \le 100$ 。

设 $F(n)=\sum\limits_{i=1}^n i^k$ ， $G(n)=\sum\limits_{i=1}^n i^k[i\perp n]$ ，则注意到：

$$F(n)=\sum_{d\mid n}d^kG(\frac{n}{d})$$

即：

$$G(n)=\sum_{d\mid n}\mu(d)d^kF(\frac{n}{d})$$

很显然 $F(n)$ 可以使用拉格朗日插值得到一个等价的 $k+1$ 次的多项式，设为 $\sum\limits_{i=0}^{k+1} f_in^i$ 。则：

$$\begin{aligned} G(n)&=\sum_{d\mid n}\mu(d)d^kF(\frac{n}{d})\\ &=\sum_{d\mid n}\mu(d)d^k\sum_{i=0}^{k+1}f_in^i\frac{1}{d^i}\\ &=\sum_{d\mid n}\sum_{i=0}^{k+1}f_in^id^{k-i}\mu(d)\\ &=\sum_{i=0}^{k+1}f_in^i\sum_{d\mid n}\mu(d)d^{k-i}\\ &=\sum_{i=0}^{k+1}f_in^i\prod_{j=1}^{w}\sum_{d=0}^{a_j}\mu(p_j^d)p_j^{d(k-i)}\\ &=\sum_{i=0}^{k+1}f_in^i\prod_{j=1}^{w}\sum_{d=0}^{1}\mu(p_j^d)p_j^{d(k-i)}\\ &=\sum_{i=0}^{k+1}f_in^i\prod_{j=1}^{w}(1-p_j^{k-i}) \end{aligned}$$

然后模拟式子就行。