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

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

在 AGC038C 的基础上可以实现 $O(n \ln n)$ 可以通过，但是可以做到线性。
$$
\begin {aligned}
ANS & = \sum _ {T = 1} ^ n T \sum _ {e | T} \mu(e)e\sum _ {i = 1} ^ {\lfloor \frac n T \rfloor } i\sum _ {i = 1} ^ {\lfloor \frac m T \rfloor } i \\
& = \sum _ {d = 1} ^ n \mu(e)e \sum _ {T = 1} ^ {\lfloor \frac n d \rfloor} eT\sum _ {i = 1} ^ {\lfloor \frac n {eT} \rfloor } i\sum _ {i = 1} ^ {\lfloor \frac m {eT} \rfloor } i\\
& = \sum _ {d = 1} ^ n \mu(e)e ^ 2\sum _ {T = 1} ^ {\lfloor \frac n d \rfloor} T\sum _ {i = 1} ^ {\lfloor \frac n {eT} \rfloor } i\sum _ {i = 1} ^ {\lfloor \frac m {eT} \rfloor } i
\end {aligned}
$$
第一层数论分块，得到相等的 $\lfloor \frac n d \rfloor$ 和 $\lfloor \frac m d \rfloor$ ，预处理 $\mu(i) i ^ 2$ 的前缀和。第二层数论分块，得到相等的 $\lfloor \frac n {eT} \rfloor $ 和 $\lfloor \frac m {eT} \rfloor $ 。

查看代码

#include <cstdio>
#include <algorithm>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    if (flag) x = ~x + 1;
}
template <class Type, class ...rest>
void read(Type &x, rest &...y) { read(x), read(y...); }
template <class Type>
void write(Type x)
{
    if (x < 0) putchar('-'), x = ~x + 1;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
typedef long long LL;
const int N = 1e7 + 10, mod = 20101009;
int n, m, f[N];
int cnt, p[N];
bool vis[N];
void init()
{
    f[1] = 1;
    vis[1] = true;
    for (int i = 2; i < N; ++i)
    {
        if (!vis[i]) p[++cnt] = i, f[i] = -1;
        for (int j = 1; i * p[j] < N; ++j)
        {
            vis[i * p[j]] = true;
            if (i % p[j] == 0)
            {
                f[i * p[j]] = 0;
                break;
            }
            f[i * p[j]] = f[i] * f[p[j]];
        }
    }
    for (int i = 1; i < N; ++i)
        f[i] = ((LL)i * i * f[i] + f[i - 1]) % mod;
}
int S (int x) { return (LL)x * (x + 1) / 2 % mod; }
int calc (int nd, int md)
{
    int res = 0;
    for (int l = 1, r; l <= nd; l = r + 1)
    {
        r = min(nd / (nd / l), md / (md / l));
        (res += (LL)(S(r) - S(l - 1)) * S(nd / l) % mod * S(md / l) % mod) %= mod;
    }
    return res;
}
int main ()
{
    init();
    read(n, m);
    if (n > m) swap(n, m);
    int res = 0;
    for (int l = 1, r; l <= n; l = r + 1)
    {
        r = min(n / (n / l), m / (m / l));
        (res += (LL)(f[r] - f[l - 1]) * calc(n / l, m / l) % mod) %= mod;
    }
    write((res + mod) % mod);
    return 0;
}