莫比乌斯反演乱写

太久没有写莫反的题，忘完了。。。 简单写写当总结

常见数论函数

\(e(x) = [x = 1]\)
\(I(x) = 1\)
\(id(x) = x\)
以上函数完全积性

\(\varphi(x) = \sum \limits_{i = 1}^{x - 1} [\gcd(i, x) == 1]\)
\(\mu = I ^{-1}\)
\(d(x) = \sum \limits_{i = 1} ^ {x} [i \mid x]\)
以上是积性函数

狄利克雷卷积

若 \(F(n) = \sum \limits_{d \mid n} f(d) * g(n / d)\)，则称 \(F = f * g\)
\(\mu * I = e\) (定义)
\(\varphi * I = id\) (\(\varphi\) 的性质， 其实是用莫反证的)
\(d = I * I\)

莫比乌斯函数

考虑 \(\mu(p ^ k)\)的值 (\(p \in primes\))
由\(\mu * I = e\)，得到\(\mu(p) = 1, \mu(p ^ 2) = -1\)，再用归纳法得到 \(k > 1\)时\(\mu(p ^ k) = 0\)
由于\(\mu\)是积性函数，所以\(\mu(n = p_1^{k_1} * p_2^{k_2} * ... p_x ^{k_x})\) = \(\mu(p_1^{k_1}) * ... *\mu(p_x ^{k_x})\)
所以有

莫比乌斯反演

已知 \(F(n) = \sum \limits_{d \mid n} f(d)\)，考虑求\(f(n)\)

由卷积定义有 \(F = f *I\), 考虑两边同时乘 \(I ^ {-1}\) 即 \(\mu\) 得到 \(F * \mu = f\)

所以 $f(n) = \sum \limits_{d \mid n} F(d) * \mu(n/d) $

拓展形式：已知 \(F(n) = \sum \limits_{n \mid d} f(d)\)
那么 \(f(n) = \sum \limits_{n \mid d} f(d) * \mu(d/n)\)

同时由于 \(\mu * I = e\),所以有 \(\sum \limits_{d \mid n} \mu(d) = [n=1]\)
又因为注意到\([n=m] = [n \mid m] * [\frac{m}{n} = 1]\)
将最后一项用代换有 \([n=m] = [n \mid m] * \sum \limits_{d \mid \frac{m}{n}} \mu(d)\)

应用

求 \(\sum \limits_{i=1}^n \sum \limits_{j=1}^n [\gcd(i,j) = 1]\)

\( \begin{aligned} 设f(n) & = \sum \limits_{i=1}^n \sum \limits_{j=1}^n [\gcd(i,j) = 1] \\ & = \sum \limits_{i=1}^n \sum \limits_{j=1}^n \sum \limits_{d \mid i,d \mid j} \mu(d)\\ & = \sum \limits_{d=1}^n \sum \limits_{d \mid i} \sum\limits_{d \mid j} \mu(d)\\ & = \sum \limits_{d=1}^n \mu(d) (n/d) ^2 \end{aligned} \)
然后对于 \(\mu\)做前缀和,对\(n/d\)整除分块即可
预处理\(O(n)\),单次询问复杂度\(O(\sqrt n)\)

求 \(\sum \limits_{i=1}^n \sum \limits_{j=1}^n [\gcd(i,j) = d]\)

等价于 \(\sum \limits_{i=1}^{n/d} \sum \limits_{j=1}^{n/d} [\gcd(i,j) = 1]\),就转化成了上一个问题

auto calc = [&](int n, int d) {
        n /= d;
        int l = 1, r = 0;
        ll ret = 0;
        for (; l <= n; l = r + 1) {
            r = std::min(n / (n / l), n);
            ret += 1ll * (sum[r] - sum[l - 1]) * (n / l) * (n / l);
        }
        return ret;
    };

求\(\sum \limits_{i=1}^n \sum \limits_{j=1}^n [\gcd(i,j) \in primes]\)

等价于 \(\sum \limits_{p \leq n, p \in primes} f(n/p)\)
复杂度是 \(O(\frac{n}{\log n})\)的,证明不会，好像要用积分

P5221 Product

\( \begin{aligned} & \prod \limits_{i=1}^n \prod \limits_{j=1}^n \frac{lcm(i,j)}{gcd(i,j)} \\ & = \prod \limits_{i=1}^n \prod \limits_{j=1}^n \frac{i * j}{gcd(i,j) ^2}\\ \end{aligned} \)

上面部分很好算，考虑下半部分的\(\prod \limits_{i=1}^n \prod \limits_{j=1}^n {gcd(i,j)}，可以枚举\gcd为\)d$的数对个数算贡献

\( \begin{aligned} & \prod \limits_{d=1}^n d ^{\sum\limits_{i=1}^n \sum \limits_{j=1}^n [\gcd(i,j)=d]}\\ & \prod \limits_{d=1}^n d ^{f(n/d)} \end{aligned} \)

然后由于\((n/d)\)的值只有\(O(\sqrt n)\)种,每次算是\(O(\sqrt n)\)的，莫反总复杂度是\(O(n)\)
总复杂度为\(O(n \log n)\)的，瓶颈在于快速幂

谴责出题人\(1e6\)只开200ms,还卡空间

#include <bits/stdc++.h>

const int MAXN = 1e6 + 5;

int mu[MAXN], pr[100005], cnt;
bool vis[MAXN];

void primes(int n) {
    mu[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            pr[++cnt] = i;
            mu[i] = -1;
        }
        for (int j = 1; j <= cnt; j++) {
            int x = i * pr[j];
            if (x > n) break;
            vis[x] = 1;
            if (i % pr[j] == 0) {
                mu[x] = 0;
                break;
            } 
            mu[x] = -mu[i];
        }
    }
    for (int i = 2; i <= n; i++) mu[i] += mu[i - 1]; 
}

#define ll long long
const int MOD = 104857601;

int power(int a, int b) {
    int ret = 1;
    for (; b; b >>= 1) {
        if (b & 1) ret = (1ll * ret * a) % MOD;
        a = (1ll * a * a) % MOD;
    }
    return ret;
}

void solve() {
    int n;
    std::cin >> n;
    primes(n + 1);
    int mul = 1, ans = 1;
    for (int i = 1; i <= n; i++) {
        mul = 1ll * mul * i % MOD;
    }
    for (int i = 1; i <= n; i++) {
        ans = 1ll * ans * power(i, n) % MOD * mul % MOD;
    }
    auto calc = [&](int x) {
        ll ret = 0;
        int l = 1, r = 0;
        for (; l <= x; l = r + 1) {
            r = std::min(x, x / (x / l));
            ret += 1ll * (mu[r] - mu[l - 1]) * (x / l) * (x / l);
        }
        ret %= (MOD - 1);
        return (int)ret;
    };

    int div = 1, tmp;
    for (int d = 1; d <= n; d++) {
        if (d == 1 || ((n / d) != (n / (d - 1)))) tmp = calc(n / d);
        div = 1ll * div * power(d, tmp) % MOD;
    }
    div = 1ll * div * div % MOD;

    ans = 1ll * ans * power(div, MOD - 2) % MOD;

    std::cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    int t = 1;
    while (t--) {
        solve();
    }

    return 0;
}