Messy

POJ2480：积性函数的运用

发表于 |

题意

输入n, 输出$\sum_{1\leq i\leq n}gcd(i,n)$。

Input Output
2 3
6 15

稳定的传送门

积性函数

对于一个函数$f(n)$,如果$f(1)=1$，且有$$f(ab)=f(a)f(b), a\perp b$$
则$f(n)$具有积性。

常见的积性函数有：

  1. 欧拉函数$φ(n)$
  2. 莫比乌斯函数$μ(n)$
  3. $gcd(n,k)$,当k固定

积性函数的性质：

  1. $n=p_1^{a_1}p_2^{a_2}…p_n^{a_n}$,则$f(n)=f(p_1^{a_1})f(p_2^{a_2})…f(p_n^{a_n})$。
  2. 积性函数的狄利克雷卷积也是积性函数。

欧拉函数

欧拉函数$\varphi (n)$是小于或等于n的正整数中与n互质的数的数目。
利用到了以下性质：
$$\varphi(n^m)=n^{m-1}\varphi(n) $$

推演

直观地，对于n=6，我们有：

$i$ $gcd(i,n)$
1 1
2 2
3 3
4 2
5 1
6 6

可以按照$gcd(i,n)$将结果分为几个部分，如$gcd(i,n)=1$时，这部分的和即为$\varphi(n)$。
对于$gcd(i,n)=k$的部分，和为$\varphi(n/k)$。
所以有
$${\sum_{1\leq i\leq n}gcd(i,n)}={\sum_{k\vert n} k\varphi(\frac{n}{k})}$$ 令${h(n)={\sum_{k\vert n} k\varphi(\frac{n}{k})}}$，可以发现这是一个积性函数。这是《具体数学》习题3.44的一个例子。 习题3.44要求证明当f和g都是积性函数的时候，$h(n)=\sum_{k\vert n} f(k)g(\frac{n}{k})$也是积性函数。这里令$f(n)=n$,$g(n)=\varphi(n)$即可。 网上很多这道题的题解直接说“积性函数的和也是积性函数”，这是错误的。 现在令$n=p_1^{a_1}p_2^{a_2}...p_n^{a_n}$,则$h(n)=h(p_1^{a_1})h(p_2^{a_2})...h(p_n^{a_n})$。 接下来研究的是$h(p^{a})$的值。 $$\begin{align*} h(p^{a})&=\sum_{k\vert p^a}k\varphi(\frac{p^a}{k})\\ &=\sum_{j=0}^{a}p^j \varphi({p^{a-j}})\\ &=p^a + \sum_{j=0}^{a-1}p^j p^{a-j-1}(p-1) \\ &=p^a + ap^{a-1}(p-1) \end{align*}$$
得到了一个只与p和a有关的式子。所以分解质因数后，根据上式计算即可。
注意，在化简的过程中，要仔细考虑$j=a$的情况。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
int main(){
    ll n;
    while (~scanf("%lld", &n)) {
        ll ans = n;
        for (ll i = 2; i * i <= n; ++i) {
            if (n % i == 0) {
                int k = 0;
                while (n % i == 0) {
                    n /= i;
                    k++;
                }
                ans += ans * k * (i - 1) /i;
            }
        }
        if (n != 1) {
            ans = ans * (n * 2 - 1)/n;
        }
        printf("%lld\n", ans);
    }
}