莫比乌斯反演

Posted on Edited on In Word count in article: 1.7k Reading time ≈ 6 mins.
莫比乌斯反演

P3911 最小公倍数之和

\[ 求\sum\limits_{i=1}^n\sum\limits_{j=1}^n{lcm(a_i,a_j)}\\ \forall a_i \in \left[ 1, \;Maxn\right] \]

思路：

\[ \sum\limits_{i=1}^n\sum\limits_{j=1}^n{lcm(a_i,a_j)}\\ \Leftrightarrow\sum\limits_{i=1}^n\sum\limits_{j=1}^n{lcm(i,j)}\cdot c_i \cdot c_j\\ {PS： c_i,\; c_j分别别表示i，j出现的次数} \]

化简：

\[ \sum\limits_{i=1}^n\sum\limits_{j=1}^nlcm(i,\;j)\cdot i \cdot j\\ \Leftrightarrow\sum\limits_{i=1}^n\sum\limits_{j=1}^n\frac{i \cdot j \cdot c_i \cdot c_j}{\gcd(i,\;j)}\\ \Leftrightarrow\sum\limits_{d=1}^n\;d\;\sum\limits_{i=1}^\left[\frac{n}{d}\right]\sum\limits_{j=1}^\left[\frac{n}{d}\right]\left[ \gcd(i,\;j) = 1\right]\cdot i \cdot j \cdot c_{id} \cdot c_{jd} \\ \Leftrightarrow\sum\limits_{d=1}^n\;d\;\sum\limits_{i=1}^\left[\frac{n}{d}\right]\sum\limits_{j=1}^\left[\frac{n}{d}\right]\sum\limits_{k\mid \gcd (i,j)}\mu(k)\cdot i\cdot j\cdot c_{id}\cdot c_{jd}\\ \Leftrightarrow\sum\limits_{d=1}^n\sum\limits_{k=1}^\left[\frac{n}{d}\right]\;d\cdot \mu(k)\sum\limits_{i=1}^\left[\frac{n}{kd}\right]\sum\limits_{j=1}^\left[\frac{n}{kd}\right] i\cdot j\cdot c_{idk}\cdot c_{jdk}\cdot k^2\\ \Leftrightarrow\sum\limits_{T=1}^nT\cdot\;(\sum\limits_{i=1}^\left[ \frac{n}{T} \right]i\cdot c_{iT})^2 \cdot \sum\limits_{k \mid T}\mu(k) \cdot k \]

然后有： \[ \sum\limits_{k \mid T}\mu(k) \cdot k \] 这个可以预处理的

代码：
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>

typedef long long ll;
const int Maxn = 5e4;
ll N, Temp, MaxNum, Ans;
ll Cnt[Maxn + 5], Mu[Maxn + 5], Pri[Maxn + 5], S[Maxn + 5], Tot;
bool Vis[Maxn + 1];

inline void Init(const int Maxn)
{
    Mu[1] = 1;
    for (int i = 2; i <= Maxn; ++i)
    {
        if (!Vis[i]) Pri[++Tot] = i, Mu[i] = -1;
        for (int j = 1; j <= Tot && i * Pri[j] <= Maxn; ++j)
        {
            Vis[i * Pri[j]] = 1;
            if (i % Pri[j]) Mu[i * Pri[j]] = -Mu[i];
            else 
            {
                Mu[i * Pri[j]] = 0;
                break;
            }
        }
    }
    for (int i = 1; i <= Maxn; ++i)
        for (int j = i; j <= Maxn; j += i) S[j] += Mu[i] * i;
}

inline void Max(ll &X, ll Y) {X = (X > Y ? X : Y);}

int main()
{
    scanf("%lld", &N);
    while (N--)
    {
        scanf("%lld", &Temp);
        Cnt[Temp]++;
        Max(MaxNum, Temp);
    }
    Init(MaxNum);
    for (ll T = 1; T <= MaxNum; ++T)
    {
        ll Temp(0);
        for (ll i = 1; i <= MaxNum / T; ++i) Temp += i * Cnt[i * T];
        Ans += T * Temp * Temp * S[T];
    }
    printf("%lld\n", Ans);
    system("pause");
}
Ps : 双倍经验AT2500

只需要在这道题的基础上减去自己的贡献再乘上2的逆元，注意取模啊！！！

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>

typedef long long ll;

const ll Maxn = 1e6, Mod = 998244353;
ll N, Temp, MaxNum, Ans, TempA;
ll Cnt[Maxn + 5], Mu[Maxn + 5], Pri[Maxn + 5], S[Maxn + 5], Tot;
bool Vis[Maxn + 1];

inline void Init(const int Maxn)
{
    Mu[1] = 1;
    for (int i = 2; i <= Maxn; ++i)
    {
        if (!Vis[i]) Pri[++Tot] = i, Mu[i] = -1;
        for (int j = 1; j <= Tot && i * Pri[j] <= Maxn; ++j)
        {
            Vis[i * Pri[j]] = 1;
            if (i % Pri[j]) Mu[i * Pri[j]] = -Mu[i];
            else 
            {
                Mu[i * Pri[j]] = 0;
                break;

            }
        }
        if (Mu[i] < 0) Mu[i] += Mod;
    }
    for (int i = 1; i <= Maxn; ++i)
        for (int j = i; j <= Maxn; j += i) S[j] = (S[j] + Mu[i] * i % Mod) % Mod;
}

inline void Max(ll &X, ll Y) {X = (X > Y ? X : Y);}

inline ll Pow(ll Y, ll X = 2)
{
    ll Ans(1);
    while (Y)
    {
        if (Y & 1) Ans = Ans * X % Mod;
        X = X * X % Mod;
        Y >>= 1;
    }
    return Ans % Mod;
}

int main()
{
    scanf("%lld", &N);
    while (N--)
    {
        scanf("%lld", &Temp);
        TempA = (TempA + Temp) % Mod;
        Cnt[Temp]++;
        Max(MaxNum, Temp);
    }
    Init(MaxNum);
    for (ll T = 1; T <= MaxNum; ++T)
    {
        ll Temp(0);
        for (ll i = 1; i <= MaxNum / T; ++i) Temp = (Temp + i * Cnt[i * T] % Mod) % Mod;
        Ans = (Ans + T * Temp % Mod * Temp % Mod * S[T] % Mod) % Mod;
    }
    printf("%lld\n", (Ans - TempA + Mod) % Mod * Pow(Mod - 2) % Mod);
    system("pause");
}

P1447 [NOI2010]能量采集

\[ 求\sum\limits_{i=1}^n\sum\limits_{j=1}^m\left[(2\cdot\gcd(i,j))-1\right] \]

思路：

\[ \sum\limits_{i=1}^n\sum\limits_{j=1}^m\left[(2\cdot\gcd(i,j))-1\right]\\\\ \Leftrightarrow\sum\limits_{i=1}^n\sum\limits_{j=1}^m 2 \cdot\gcd(i,j) - m\cdot n\\\\ \Leftrightarrow2\cdot\sum\limits_{d=1}^nd\;\cdot\sum\limits_{i=1}^\left[\frac{n}{d}\right]\sum\limits_{j=1}^\left[\frac{m}{d}\right]\left[\gcd(i,j)=1\right]-m\cdot n\\\\ \Leftrightarrow2\cdot\sum\limits_{d=1}^nd\;\cdot\sum\limits_{i=1}^\left[\frac{n}{d}\right]\sum\limits_{j=1}^\left[\frac{m}{d}\right]\sum\limits_{k\mid\gcd(i,j)}\mu(k)-m\cdot n\\\\ \Leftrightarrow2\cdot\sum\limits_{d=1}^nd\cdot\sum\limits_{k=1}^\left[\frac{n}{d}\right]\mu(k)\cdot\left[\frac{n}{dk}\right]\cdot\left[\frac{m}{dk}\right]-m\cdot n\\\\ \Leftrightarrow2\cdot\sum\limits_{T=1}^n\left[\frac{n}{T}\right]\cdot\left[\frac{m}{T}\right]\sum\limits_{d\mid T}^\left[\frac{n}{T}\right]d\cdot\mu(\frac{T}{d})-m\cdot n\\\\ \]

化简：

\[ 令：h(n) = \sum\limits_{d\mid T}^\left[\frac{n}{T}\right]d\cdot\mu(\frac{T}{d})\\\\ h=id*\mu\\\\ \because \mu * 1=\epsilon\\\\ \therefore h*1=id* (\mu * 1)\\\\ \therefore h*1=id*\epsilon\\\\ \therefore h*1=id\\\\ 又\because id = \varphi * 1\\\\ \therefore h = \varphi\\\\ 即：2\cdot\sum\limits_{T=1}^n\left[\frac{n}{T}\right]\cdot\left[\frac{m}{T}\right]\sum\limits_{d\mid T}^\left[\frac{n}{T}\right]d\cdot\mu(\frac{T}{d})-m\cdot n\\\\ \Leftrightarrow2\cdot\sum\limits_{T=1}^n\varphi(T)\cdot\left[\frac{n}{T}\right]\cdot\left[\frac{m}{T}\right]-m\cdot n \]

代码：
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int Maxn = 1e5;
ll N, M, Ans, Cnt;
ll Phi[Maxn + 10], Pri[Maxn + 10];
bool Vis[Maxn + 10];

inline void Init()
{
    Phi[1] = 1;
    for (int i = 2; i <= Maxn; ++i)
    {
        if (!Vis[i]) Phi[i] = i - 1, Pri[++Cnt] = i;
        for (int j = 1; j <= Cnt && i * Pri[j] <= Maxn; ++j)
        {
            Vis[i * Pri[j]] = 1;
            if (i % Pri[j]) Phi[i * Pri[j]] = Phi[i] * Phi[Pri[j]];
            else 
            {
                Phi[i * Pri[j]] = Phi[i] * Pri[j];
                break;
            }
        }
    }
    for (int i = 1; i <= Maxn; ++i) Phi[i] += Phi[i - 1];
}

int main()
{
    Init();
    scanf("%lld %lld", &N, &M);
    if (N > M) swap(N, M);
    for (int l = 1, r; l <= N; l = r + 1)
    {
        r = min(N / (N / l), M / (M / l));
        Ans += 2 * (Phi[r] - Phi[l - 1]) * (N / l) * (M / l);
    }
    printf("%lld", Ans - N * M);
    system("pause");
}

P5221 Product

\[ 求:\prod\limits_{i=1}^N\prod\limits_{j=1}^N\frac{lcm(i,j)}{\gcd(i,j)}(mod\;104857601) \]

思路:

\[ \prod\limits_{i=1}^N\prod\limits_{j=1}^N\frac{\operatorname{lcm}(i,j)}{\gcd(i,j)}\\ \Leftrightarrow\prod\limits_{i=1}^N\prod\limits_{j=1}^N\frac{i\cdot j}{\gcd(i,j)^2}\\ \Leftrightarrow\prod\limits_{i=1}^N\prod\limits_{j=1}^Ni\cdot j\prod\limits_{i=1}^N\prod\limits_{j=1}^N\frac{1}{\gcd(i,j)^2}\\ \]

化简:

\[ 其中:\prod\limits_{i=1}^N\prod\limits_{j=1}^Ni\cdot j \\=\prod\limits_{i=1}^N\left(i^N\cdot N!\right)\\ =\left(N!\right)^N\prod\limits_{i=1}^Ni^N\\ =\left(N!\right)^N\cdot\left(N!\right)^N\\ =\left(N!\right)^{2N} \]

\[ 其中还有:\prod\limits_{i=1}^N\prod\limits_{j=1}^N\frac{1}{\gcd(i,j)^2}\\ =\prod\limits_{d=1}^N\prod\limits_{i=1}^N\prod\limits_{j=1}^N\frac{1}{d^2\cdot\left[\gcd(i,j)=d\right]}\\ 若:gcd(i,j)\ne d\;则整体贡献为1\\ =\left(\prod\limits_{d=1}^Nd^{\sum\limits_{i=1}^N\sum\limits_{j=1}^N\left[\gcd(i, j)=d\right]}\right)^{-2}\\ =\left(\prod\limits_{d=1}^Nd^{\sum\limits_{i=1}^\frac{N}{d}\sum\limits_{j=1}^\frac{N}{d}\left[\gcd(i, j)=1\right]}\right)^{-2}\\ 令:sum(x) = \sum\limits_{i=1}^x\varphi(i)\\ =\left(\prod\limits_{d=1}^Nd^{2sum(\frac{N}{d}) - 1}\right)^{-2}\\ \therefore Ans = (N!)^{2N}\left(\prod\limits_{d=1}^Nd^{2sum(\frac{N}{d}) - 1}\right)^{-2} \]

代码:
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>

using namespace std;

const int Maxn = 1e6, Mod = 104857601;
int N, Cnt, Phi[Maxn + 5], Fac(1), Tmp(1), Pri[Maxn/2];
bool Vis[Maxn + 5];

inline int Pow(int X, int Y)
{
    Y %= (Mod - 1);
    int Ans(1);
    while (Y)
    {
        if (Y & 1) Ans = 1ll * Ans * X % Mod;
        X = 1ll * X * X % Mod;
        Y >>= 1; 
    }
    return Ans % Mod;
    
}

inline void Init(const int Maxn)
{
    Phi[1] = 1;
    for (int i = 2; i <= Maxn; ++i)
    {
        Fac = 1ll * Fac * i % Mod;
        if (!Vis[i]) Pri[++Cnt] = i, Phi[i] = i - 1;
        for (int j = 1; j <= Cnt && i * Pri[j] <= Maxn; ++j)
        {
            Vis[i * Pri[j]] = 1;
            if (i % Pri[j]) Phi[i * Pri[j]] = Phi[i] * (Pri[j] - 1);
            else 
            {
                Phi[i * Pri[j]] = Phi[i] * Pri[j];
                break;
            }
        }
    }
    for (int i = 1; i <= Maxn; ++i) Phi[i] = ( Phi[i - 1] + 2ll * Phi[i]) % (Mod - 1);
    for (int i = 2; i <= Maxn; ++i) Tmp = 1ll * Tmp * Pow(i, Phi[Maxn / i] - 1) % Mod;
    Fac = Pow(Fac, Maxn * 2);
    Tmp = 1ll * Pow(1ll * Tmp * Tmp % Mod, Mod - 2) * Fac % Mod;
}

int main()
{
    scanf("%d", &N);
    Init(N);
    printf("%d\n", Tmp);
    system("pause");
}