积性函数

定义

$\forall (a,b)=1,f(ab)=f(a)f(b)$

常见的积性函数

欧拉函数 $\varphi(x)$，莫比乌斯函数 $\mu(x)$，最大公因数 $\gcd(x,k)$($k$固定)，正因子数目 $d(x)$ ，正因子之和 $\sigma(x)$，常函数，单位函数 $Id(x)=x$，幂函数 $Idk(x) =n ^ k$，等

下面以莫比乌斯函数和欧拉函数为例证明积性函数：

莫比乌斯函数证明：

设$a=p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$，$b=q_1^{\beta_1} q_2^{\beta_2} \cdots q_k^{\beta_t}$ ，$ab=p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}q_1^{\beta_1} \cdots q_k^{\beta_t}$
若 $ \exists \alpha_i \ge 2$，则$\mu(a)=\mu(ab)=0$，成立，同理，若 $\exists \beta_i \ge 2$ 也成立。

若 $\forall \alpha_i,\beta_i=1$，则$\mu(a)=(-1)^k,\mu(b)=(-1)^t,\mu(ab)=(-1)^{k+t}$，满足 $\mu(ab)=\mu(a)\mu(b)$。

综上，莫比乌斯函数是积性函数。

欧拉函数证明：

$\varphi(n)=n\prod_{i=1}^k(1-\frac 1 {p_i})$

设$a=p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$，$b=q_1^{\beta_1} q_2^{\beta_2} \cdots q_k^{\beta_t}$ ，$ab=p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}q_1^{\beta_1} \cdots q_k^{\beta_t}$

$\varphi(a)=a\prod_{i=1}^k(1-\frac 1 {p_i})$，$\varphi(b)=b\prod_{i=1}^t(1-\frac 1 {q_i})$

$\varphi(ab)=ab\prod_{i=1}^k(1-\frac 1 {p_i})\prod_{i=1}^t(1-\frac 1 {q_i})=[a\prod_{i=1}^k(1-\frac 1 {p_i})][b\prod_{i=1}^t(1-\frac 1 {q_i})]=\varphi(a)\varphi(b)$

所以，欧拉函数是积性函数。

例题：洛谷 P2303 [SDOI2012] Longge 的问题/AcWing 221. 龙哥的问题

龙哥现在有一道题，要考考大家。

给定一个整数 $ N $，请你求出 $ \sum_{1 \le i \le N} gcd(i，N) $的值。

输入格式

一个整数 $ N $。

输出格式

一个整数表示结果。

数据范围

$ 1 < N < 2^{31} $

输入样例：

1

6

输出样例：

1

15

分析：

考虑满足 $(i,n)=d$ 的 $i$ 共多少种。

$(i,n)=d \Longleftrightarrow (\frac i d,\frac n d)=1$

记 $i’= \frac i d,n’=\frac n d$，则原式等价于 $(i’,n’)=1$，因此满足条件的 $i$ 有 $\varphi(n’)=\varphi(\frac n d)$ 种，所以：

$\sum_{i=1}^n(i,n)=\sum_{d|n} d\cdot \varphi(\frac n d) $

$d,\frac n d$ 两两配对，记 $d’=\frac n d$

$\sum_{d|n} d\cdot \varphi(\frac n d)=\sum_{d’|n} \frac n d’ \cdot \varphi(d’)=\sum_{d|n} \frac n d d \prod_{i=1}^{k}(1-\frac 1 {p_i})=n\sum_{d|n}\prod_{i=1}^k(1-\frac 1 {p_i})$

设 $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k},d=p_1^{\beta_1}p_2^{\beta_2}\cdots p_k^{\beta_k}$

则所有约数就是 $(p_1^0+p_1^1+\cdots + p_1^{\alpha_1})(p_2^0+p_2^1+\cdots + p_2^{\alpha_2})\cdots(p_k^0+p_k^1+\cdots + p_k^{\alpha_k})$ 展开的每一项，$[1+(1-\frac 1 {p_1})+(1-\frac 1 {p_1})+\cdots][1+(1-\frac 1 {p_2})+\cdots]\cdots[1+(1-\frac 1 {p_k})+\cdots]$ 展开的每一项就是前一个式子每一项对应约数对应的 $\prod_{i=1}^k(1-\frac 1 {p_i})$ 的值，而 $\sum_{d|n}\prod_{i=1}^k(1-\frac 1 {p_i})$ 对应的就是所有约数的对应 $\prod_{i=1}^k(1-\frac 1 {p_i})$ 之和，也就是 $[1+(1-\frac 1 {p_1})+(1-\frac 1 {p_1})+\cdots][1+(1-\frac 1 {p_2})+\cdots]\cdots[1+(1-\frac 1 {p_k})+\cdots]$

$[1+(1-\frac 1 {p_1})+(1-\frac 1 {p_1})+\cdots][1+(1-\frac 1 {p_2})+\cdots]\cdots[1+(1-\frac 1 {p_k})+\cdots]=\prod_{i=1}^k (1+\alpha_i(1-\frac 1 {p_i}))$

所以原式就是 $n\prod_{i=1}^k (1+\alpha_i(1-\frac 1 {p_i}))=n\prod_{i=1}^k \frac{p_i+p_i\alpha_i-\alpha_i}{p_i}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int main(){
    ll n;
    cin >> n;
    ll res=n;
    for(ll i=2;i<=n/i;i++){
        if(n%i==0){
            ll a=0,p=i;
            while(n%p==0)a++,n/=p;
            res=res*(p+1ll*a*p-a)/p;
        }
    }
    if(n>1){
        res=res*(n+n-1)/n;
    }
    
    cout << res << endl;
    return 0;
}