「MCOI-02」Convex Hull 凸包-题解

· · 题解

Subtask 1

直接暴力计算即可。时间复杂度为 O(nm(\sqrt{n} + \sqrt{m}))。

代码：

#include <stdio.h>
#include <math.h>

inline int tau(int n){
    int t = sqrt(n), ans = 0;
    for (register int i = 1; i <= t; i++){
        if (n % i == 0){
            ans++;
            if (i * i != n) ans++;
        }
    }
    return ans;
}

int gcd(int a, int b){
    return b == 0 ? a : gcd(b, a % b);
}

int main(){
    int n, m, p, ans = 0;
    scanf("%d %d %d", &n, &m, &p);
    for (register int i = 1; i <= n; i++){
        for (register int j = 1; j <= m; j++){
            ans = (ans + tau(i) * tau(j) % p * tau(gcd(i, j)) % p) % p;
        }
    }
    printf("%d", ans);
    return 0;
}

Subtask 2

前置芝士：莫比乌斯反演

我们先来化简原式。

原式 = \displaystyle\sum_{d = 1}^{\min(n, m)} \tau(d) \sum_{i = 1}^n \sum_{j = 1}^m [\gcd(i, j) = d] \tau(i) \tau(j)

= \displaystyle\sum_{d = 1}^{\min(n, m)} \tau(d) \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor} [\gcd(i, j) = 1] \tau(id) \tau(jd) = \displaystyle\sum_{d = 1}^{\min(n, m)} \tau(d) \sum_{i = 1}^{\lfloor \frac{n}{d} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{d} \rfloor} \tau(id) \tau(jd) \sum_{q\ | \gcd(i, j)} \mu(q) = \displaystyle\sum_{d = 1}^{\min(n, m)} \tau(d) \sum_{q = 1}^{\lfloor \frac{\min(n, m)}{d} \rfloor} \mu(q) \sum_{i = 1}^{\lfloor \frac{n}{dq} \rfloor} \sum_{j = 1}^{\lfloor \frac{m}{dq} \rfloor} \tau(idq) \tau(jdq) = \displaystyle\sum_{d = 1}^{\min(n, m)} \tau(d) \sum_{q = 1}^{\lfloor \frac{\min(n, m)}{d} \rfloor} \mu(q) \sum_{i = 1}^{\lfloor \frac{n}{dq} \rfloor} \tau(idq) \sum_{j = 1}^{\lfloor \frac{m}{dq} \rfloor} \tau(jdq) = \displaystyle\sum_{d = 1}^{\min(n, m)} \tau(d) \sum_{q = 1}^{\lfloor \frac{\min(n, m)}{d} \rfloor} \mu(q) \sum_{dq\ |\ i}^n \tau(i) \sum_{dq\ |\ j}^m \tau(j)

预处理 \mu 和 \tau 函数的值，然后直接计算即可。时间复杂度暂时无法确定，希望有读者能给出合理的时间复杂度并在评论中回复我。

代码：

#include <stdio.h>

typedef long long ll;

const int N = 2e6 + 7;
int prime[N], mu[N], tau[N];
bool p[N];

inline void init(int n){
    int cnt = 0;
    p[0] = p[1] = true;
    mu[1] = 1;
    tau[1] = 1;
    for (register int i = 2; i <= n; i++){
        if (!p[i]){
            prime[++cnt] = i;
            mu[i] = -1;
            tau[i] = 2;
        }
        for (register int j = 1; j <= cnt && i * prime[j] <= n; j++){
            int t = i * prime[j];
            p[t] = true;
            if (i % prime[j] == 0){
                mu[t] = 0;
                tau[t] = tau[i] * 2 - tau[i / prime[j]];
                break;
            }
            mu[t] = -mu[i];
            tau[t] = tau[i] * 2;
        }
    }
}

inline int min(int a, int b){
    return a < b ? a : b;
}

inline int f(int n, int k, int mod){
    int ans = 0;
    for (register int i = k; i <= n; i += k){
        ans = (ans + tau[i]) % mod;
    }
    return ans;
}

inline ll g(int n, int m, int k, int mod){
    int nc = n / k, mc = m / k, nmc = min(nc, mc);
    ll ans = 0;
    for (register int i = 1; i <= nmc; i++){
        int t = i * k;
        ans = ((ans + (ll)mu[i] * f(n, t, mod) % mod * f(m, t, mod) % mod) % mod + mod) % mod;
    }
    return ans;
}

inline int max(int a, int b){
    return a > b ? a : b;
}

int main(){
    int n, m, p, nm;
    ll ans = 0;
    scanf("%d %d %d", &n, &m, &p);
    nm = min(n, m);
    init(max(n, m));
    for (register int i = 1; i <= nm; i++){
        ans = (ans + tau[i] * g(n, m, i, p) % p) % p;
    }
    printf("%lld", ans);
    return 0;
}

Subtask 3 & 4

我们继续在 Subtask 2 的基础上化简原式。

原式 = \displaystyle\sum_{T = 1}^{\min(n, m)} (\sum_{q\ |\ T} \mu(q) \tau(\frac{T}{q})) \sum_{T\ |\ i}^n \tau(i) \sum_{T\ |\ j}^m \tau(j)

由于 \tau = 1 \times 1，所以 \mu \times \tau = \mu \times 1 \times 1 = \varepsilon \times 1 = 1，所以 \displaystyle\sum_{q\ |\ T} \mu(q) \tau\left(\frac{T}{q}\right) 的值恒为 1。

∴ 原式 = \displaystyle\sum_{T = 1}^{\min(n, m)} \sum_{T\ |\ i}^n \tau(i) \sum_{T\ |\ j}^m \tau(j)

预处理 \tau 函数的值，然后直接计算即可。时间复杂度为 O(\ln \min(n, m)(n + m))。

代码：

#include <stdio.h>

typedef long long ll;

const int N = 2e6 + 7;
int prime[N], tau[N];
bool p[N];

inline void init(int n){
    int cnt = 0;
    p[0] = p[1] = true;
    tau[1] = 1;
    for (register int i = 2; i <= n; i++){
        if (!p[i]){
            prime[++cnt] = i;
            tau[i] = 2;
        }
        for (register int j = 1; j <= cnt && i * prime[j] <= n; j++){
            int t = i * prime[j];
            p[t] = true;
            if (i % prime[j] == 0){
                tau[t] = tau[i] * 2 - tau[i / prime[j]];
                break;
            }
            tau[t] = tau[i] * 2;
        }
    }
}

inline int min(int a, int b){
    return a < b ? a : b;
}

inline int f(int n, int k, int mod){
    int ans = 0;
    for (register int i = k; i <= n; i += k){
        ans = (ans + tau[i]) % mod;
    }
    return ans;
}

inline int max(int a, int b){
    return a > b ? a : b;
}

int main(){
    int n, m, p, nm;
    ll ans = 0;
    scanf("%d %d %d", &n, &m, &p);
    nm = min(n, m);
    init(max(n, m));
    for (register int i = 1; i <= nm; i++){
        ans = (ans + (ll)f(n, i, p) * f(m, i, p) % p) % p;
    }
    printf("%lld", ans);
    return 0;
}