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


题意

求所有 \(\le n\) 且与 \(n\) 互质的数的 \(m\) 次幂的和。

分析

题目要求的就是 \(\sum_{i=1}^n i^m [gcd(i,n)=1]\) 。

用莫比乌斯反演 \(\sum_{i=1}^n i^m \sum_{d|i,n}\mu (d)\) 。

变换求和的顺序 \(\sum_{d|n}\mu(d) d^m\sum_{i=1}^{\frac{n}{d}}i^m\) 。

显然 \(\sum_{d|n}\mu(d) d^m\) 这部分是积性函数。于是考虑变换后一部分。

我们令 \(f(n)=\sum_{i=1}^{n}i^m\) ,显然这是一个关于 \(n\) 的 \(m+1\) 次多项式,于是可以用拉格朗日插值把系数都求出来,变成 \(f(n)=\sum_{i=0}^{m+1}x_in^i\) 。

于是原式就变成了 \(\sum_{d|n}\mu(d) d^m\sum_{i=0}^{m+1}x_i(\frac{n}{d})^i\) 。

变换求和顺序变成 \(\sum_{i=0}^{m+1}x_i \sum_{d|n}\mu(d) d^m(\frac{n}{d})^i\) 。

显然 \(\sum_{d|n}\mu(d) d^m(\frac{n}{d})^i\) 是一个卷积的形式。

因为 \(\mu(d) d^m\) 和 \((\frac{n}{d})^i\) 都是积性函数,那么 \(\sum_{d|n}\mu(d) d^m(\frac{n}{d})^i\) 也是一个积性函数。

我们令 \(g(n)=\sum_{d|n}\mu(d) d^m(\frac{n}{d})^i\) ,且有 \(n=p_1^{a_1}\times p_2^{a_2}\times \cdots \times p_w^{a_w}\) 。那么有 \(g(n)=g(p_1^{a_1})\times g(p_2^{a_2})\times \cdots \times g(p_w^{a_w})\)

考虑对于任意的 \(g(p_i^{a_i})=\sum_{d|p_i^{a_i}}\mu(d) d^m(\frac{p_i^{a_i}}{d})^i\) ,只有当 \(d=1\) 或者 \(d=p_i\) 的时候 \(\mu(d)\neq 0\) 于是只需要求这两项,即 \(g(p_i^{a_i})=({p_i^{a_i}})^i-p_i^m(p_i^{a_i-1})^i\) 。

 

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 67,592

Categories

Archive

Comments