积性函数

· · 个人记录

积性函数

定义:

**凡是积性函数都可以使用线性筛法来求。** **常见的积性函数:** - 1. 莫比乌斯函数 $~~~\mu(x)$。 - 2. 最大公约数 $~~~gcd(x, y)$。 - 3. $n$的正因子的数量 $~~~d(n)$。 - 4. $n$的所有正因子之和 $ ~~~o(n)$。 - 5. 因子函数， $n$ 的所有正因子的$k$次幂之和，当中的$k$可以为任何复数。 - 6. 欧拉函数 $~~~\varphi(n)$。 ## ***证明*** **莫比乌斯函数证明是积性函数:** $$ n = p_1^{d_1}p_2^{d_2}p_3^{d_3}···p_n^{d_k}$$ $$ m = p_1^{a_1}p_2^{a_2}p_3^{a_3}···p_n^{a_t} $$ - 因为$n$和$m$两两互质，所以$p_i$上下的两两不同。 $$nm = p_1^{a_1}p_2^{a_2}p_3^{a_3}···p_n^{a_k}\space\space and\space\space p_1^{d_1}p_2^{d_2}p_3^{d_3}···p_n^{d_t}$$ - 如果某一个 $a_i$ 或者 $d_i$ 大于等于 $2$ ，那么$\mu(nm) = 0$ ；此时，正好满足 $\mu(nm) = \mu(n)\mu(m)$。 - 如果全都是$1$的话， $\mu(nm)=\mu(n)\mu(m) = (-1)^{k + t} = \mu(n)\mu(m)$ ，也是满足条件的。 *因此莫比乌斯函数是一个积性函数* <br /> **欧拉函数证明是积性函数**: $$ n = p_1^{d_1}p_2^{d_2}p_3^{d_3}···p_n^{d_k}$$ $$ m = p_1^{a_1}p_2^{a_2}p_3^{a_3}···p_n^{a_t} $$ - 因为$n$和$m$是两两互质的，所以: $$ \varphi(nm) = nm\prod_{i = 1}^k(1 - \frac{1}{p_i}) \space \prod_{j = 1}^t(1 - \frac{1}{p_j}) $$ $$ = n\prod_{i = 1}^k(1 - \frac{1}{p_i}) \space\space m\prod_{j = 1}^t(1 - \frac{1}{p_j}) $$ - 由此可见，左边的一项其实就是$\varphi(n)$ ，右边的一项就是$\varphi(m)$ , 所以有 $ \varphi(nm) = \varphi(n)\varphi(m) $, 即欧拉函数是积性函数。 $Add:$ 积性函数的逆也是积性函数,可以通过狄利克雷证明（我不会 ## Question: [Luogu Longge的问题](https://www.luogu.com.cn/problem/P2303) - 重点利用 $gcd(n, m)$ 的**积性函数**的性质 现学现卖（逃 $$ \sum_{i = 1}^ngcd(i, n) $$ $$ = \sum_{d | n} d\varphi(\frac{n}{d}) $$ --- ### 推导过程 $$ t(x) = \sum_{i = 0}^n[\gcd(i,n) == x] = \sum_{i = 1}^{\left\lfloor\frac{n}{x}\right\rfloor}[\gcd(i, \left\lfloor \frac{n}{x} \right\rfloor) == 1] $$ $ \varphi(x) = \sum_{i = 1}^n[\gcd(i, n) == 1] t(x) =\varphi(\left\lfloor \frac{n}{x} \right\rfloor) \space\space\space\space\space\sum_{i = 1}^ngcd(i,n) = \sum_{d | n} d \sum_{i = 1}^n [gcd(i,n) = d] = \sum_{d | n}d\varphi(n / d) ~~~ 
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int gcd(int a, int b)
{
    if (!b) 
        return a;
    else
        return gcd(b, a % b);
}
int n;
int ans;
inline int phi(int x)
{
    int ans = x;
    for (int i = 2; i * i <= x; i ++ )
        if (x % i == 0)
        {
            ans = ans / i * (i - 1);
            while (x % i == 0) x = x / i;
        }
    if (x > 1) ans = ans / x * (x - 1);
    return ans;
}
signed main()
{
    cin >> n;
    for (int i = 1; i * i<= n; i ++ )
    {
        if (n % i == 0)
        {
            ans += i * phi(n / i);
            if (i * i != n)   
                ans += (n / i) * phi(n / (n / i));
        }
    }
    cout << ans << endl;
    return 0;
}

Luogu P2257 YY的GCD

题目要求

\sum_{x = 1}^N\sum_{y = 1}^M[gcd(x, y) \in prime]

定义一下这两个重要的函数：

f(n) = \sum_{x = 1}^N\sum_{y = 1}^M[gcd(x, y) = n] F(n) = \sum_{n | d}f(d) F(n) = \sum_{x = 1}^N\sum_{y = 1}^M [n | gcd(x, y)]

重要性质利用:

\sum_{d | n}\mu(d) = [n = 1] \sum_{k \in prime}\sum_{x = 1}^N\sum_{y = 1}^M[gcd(x, y) = k] \sum_{k \in prime}\sum_{x = 1}^{\left\lfloor\frac{N}{k}\right\rfloor}\sum_{y = 1}^{\left\lfloor\frac{M}{k}\right\rfloor}[gcd(x, y) == 1] \sum_{k = 1}^N\sum_{x = 1}^{\left\lfloor\frac{N}{k}\right\rfloor}\sum_{y = 1}^{\left\lfloor\frac{M}{k}\right\rfloor}\sum_{d | gcd(x, y)}\mu(d)(k \in prime) \sum_{k = 1}^N\sum_{x = 1}^{\left\lfloor\frac{N}{k}\right\rfloor}\sum_{y = 1}^{\left\lfloor\frac{M}{k}\right\rfloor}\sum_{d | x, d | y}\mu(d)(k \in prime)

下面是最关键的转化：

\sum_{k = 1}^n \sum_{d = 1}^{\left\lfloor\frac{N}{k}\right\rfloor}\mu(d) * \left\lfloor\frac{N}{kd}\right\rfloor\left\lfloor\frac{M}{kd}\right\rfloor (k \in prime)

设:

t = kd

则有:

\sum_{k = 1}^n \sum_{d = 1}^{\left\lfloor\frac{N}{k}\right\rfloor}\mu(\frac{t}{k}) * \left\lfloor\frac{N}{t}\right\rfloor\left\lfloor\frac{M}{t}\right\rfloor (k \in prime) \sum_{t = 1}^N\left\lfloor\frac{N}{t}\right\rfloor\left\lfloor\frac{M}{t}\right\rfloor \sum_{k | t, k \in prime}\mu(\frac{t}{k}) 
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e7;
const int M = 1e7;

int n, m;
int T;
int prime[N], mu[N], cnt;
bool st[N];
int sum[N];
int f[N];

inline void init()
{
    mu[1] = 1;
    for (int i = 2; i <= M; i ++ )
    {
        if (!st[i])
        {
            prime[ ++ cnt] = i;
            mu[i] = -1;
        }
        for (int j = 1; prime[j] * i <= M; j ++ )
        {
            st[prime[j] * i] = true;
            if (i % prime[j] == 0) 
                break;
            mu[prime[j] * i] = -mu[i];
        }
    }

    for (int i = 1; i <= cnt; i ++ ) // 这里是用来预处理 μ 的
        for (int j = 1; prime[i] * j <= M; j ++ )
            f[j * prime[i]] += mu[j];

    for (int i = 1; i <= M; i ++ )
        sum[i] = sum[i - 1] + f[i];
}

inline int g(int k, int x) 
{
    return k / (k / x);
}

signed main()
{
    init();
    cin >> T;
    while (T -- )
    {
        cin >> n >> m;
        int k = min(n, m);
        int res = 0;    
        for (int l = 1, r; l <= k; l = r + 1)
        {
            r = min(k, min(g(n, l), g(m, l))); // 确定块长
            res += (sum[r] - sum[l - 1]) * (n / l) * (m / l);
        }
        cout << res << endl;
    }

    return 0;
}