题解 P1829 【[国家集训队]Crash的数字表格 / JZPTAB】

· · 题解

分析

首先，设n\leq m，要求的式子是：

\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i, j)

即

\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{i*j}{gcd(i, j)}

提个gcd出来：

\sum_{d=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{i*j}{d}[gcd(i,j)=d]

约掉d：

\sum_{d=1}^{n}d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}i*j[gcd(i,j)=1]

由

\sum_{n|d}\mu(n)=[d==1]

得原式：

\sum_{d=1}^{n}d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}i*j\sum_{a|gcd(i,j)}\mu(a)

合并：

\sum_{d=1}^{n}d\sum_{t=1}^{\lfloor\frac{n}{d}\rfloor}t^2\mu(t)*S(\lfloor\frac{n}{dt}\rfloor)*S(\lfloor\frac{m}{dt}\rfloor)

其中

S(n)=\frac{n*(n+1)}{2}

使dt=T，把他拉到前面：

\sum_{T=1}^{n}S(\lfloor\frac{n}{T}\rfloor)*S(\lfloor\frac{m}{T}\rfloor)*\sum_{ab=T}a*b^2\mu(b)

即

\sum_{T=1}^{n}S(\lfloor\frac{n}{T}\rfloor)*S(\lfloor\frac{m}{T}\rfloor)*T*\sum_{b|T}b*\mu(b)

设f(T)=\sum_{b|T}b*\mu(b)，易知f(n)为积性函数，且

f(p)=1-p, f(p^k)=f(p)\quad(p\in prime)

做法

线性筛出f(n)，预处理出T*f(T)的前缀和，原式用数论分块算即可。

代码

#include <algorithm>
#include <iostream>

using namespace std;
constexpr long long kcz = 20101009;

int v[10000001], p[10000001], pc;
long long g[10000001];

void preproc(int n)
{
    g[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        if(!v[i]) p[++pc] = i, g[i] = (1 - i) % kcz;
        for(int j = 1; j <= pc && i * p[j] <= n; j++)
        {
            v[i * p[j]] = true;
            if(!(i % p[j]) && (g[i * p[j]] = g[i])) break;
            g[i * p[j]] = (g[i] * g[p[j]]) % kcz;
        }
    }
    for(int i = 2; i <= n; i++)
        (g[i] = g[i] * i % kcz + g[i - 1]) %= kcz;
}

inline long long s(long long k)
{
    return (k * (k + 1) / 2) % kcz;
}

int main()
{
    preproc(10000000);
    int n, m;
    long long ret = 0;
    scanf("%d%d", &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));
        (ret += (((s(n / l) * s(m / l)) % kcz) * (g[r] - g[l - 1] + kcz) % kcz) % kcz + kcz) %= kcz;
    }
    printf("%lld\n", ret);
}