Luogu P6810 「MCOI-02」Convex Hull 凸包

题目描述

https://www.luogu.com.cn/problem/P6810

简要题意：求 $\sum_{i=1}^n\sum_{j=1}^m\tau(i)\tau(j)\tau((i,j))$

$n,m\le 2\times 10^6$

Solution

$$\begin{aligned} ans&=\sum_{i=1}^n\sum_{j=1}^m\tau(i)\tau(j)\tau((i,j))\\ &=\sum_{t=1}^n\sum_{i=1}^n\sum_{j=1}^n\tau(i)\tau(j)\tau(t)[(i,j)=t]\\ &=\sum_{t=1}^n\sum_{i=1}^{\lfloor\frac{n}{t}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{t}\rfloor}\tau(it)\tau(jt)\tau(t)\sum_{d|(i,j)}\mu(d)\\ &=\sum_{t=1}^n\tau(t)\sum_{d=1}^{\lfloor\frac{n}{t}\rfloor}\mu(d)\sum_{i=1}^{\lfloor\frac{n}{dt}\rfloor}\tau(idt)\sum_{j=1}^{\lfloor\frac{m}{dt}\rfloor}\tau(jdt)\\ &=\sum_{T=1}^n\sum_{i=1}^{\lfloor\frac{n}{T}\rfloor}\tau(iT)\sum_{j=1}^{\lfloor\frac{m}{T}\rfloor}\tau(jT)\sum_{t|T}\tau(t)\mu(\frac{T}{t}) \end{aligned}$$

我们考虑后面那个东西 $\sum_{d|n}\tau(d)\mu(\frac{n}{d})$，这个东西就是 $I\circ I\circ \mu$ 显然等于 $I$

那么我们只需要求 $\sum_{T=1}^n\sum_{i=1}^{\lfloor\frac{n}{T}\rfloor}\tau(iT)\sum_{j=1}^{\lfloor\frac{m}{T}\rfloor}\tau(jT)$

注意到这个东西就是 $\sum_{T=1}^n(\sum_{d|i}^n\tau(d))(\sum_{d|i}^m\tau(d))$，这是个狄利克雷后缀和的形式

可以做到 $O(n\log\log n)$

#include <iostream>
#define maxn 2000010
using namespace std;

int n, m, p;

inline int add(int x, int y) { return (x += y) >= p ? x - p : x; } 

int pri[maxn], cnt, num[maxn], d[maxn]; bool isp[maxn]; 
void init_isp(int n) {
    d[1] = 1; 
    for (int i = 2; i <= n; ++i) {
        if (!isp[i]) pri[++cnt] = i, num[i] = 1, d[i] = 2;
        for (int j = 1; j <= cnt && i * pri[j] <= n; ++j) {
            isp[i * pri[j]] = 1;
            if (i % pri[j] == 0) {
                d[i * pri[j]] = d[i] / (num[i] + 1) * (num[i] + 2);
                num[i * pri[j]] = num[i] + 1; break;
            }
            d[i * pri[j]] = d[i] * 2;
            num[i * pri[j]] = 1; 
        }
    }
}

int f[maxn], g[maxn];
int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m >> p;
    if (n > m) swap(n, m); init_isp(m);
    for (int i = 1; i <= n; ++i) f[i] = d[i];
    for (int i = 1; i <= m; ++i) g[i] = d[i];
    for (int i = 1; i <= cnt; ++i) 
        for (int j = n / pri[i]; j; --j) f[j] = add(f[j], f[j * pri[i]]);
    for (int i = 1; i <= cnt; ++i) 
        for (int j = m / pri[i]; j; --j) g[j] = add(g[j], g[j * pri[i]]);
    int ans = 0;
    for (int i = 1; i <= n; ++i) ans = add(ans, 1ll * f[i] * g[i] % p);
    cout << ans << "\n";
    return 0; 
}