『题解』Luogu-P5572 [CmdOI2019]简单的数论题

· · 题解

P5572 [CmdOI2019]简单的数论题

思路基本同 P4240 毒瘤之神的考验。

Description

Solution

不妨设 n\le m。

\begin{aligned} ans & = \sum_{d = 1}^n \sum_{i = 1}^n \sum_{j = 1}^m \varphi\left(\dfrac{ij}{d^2} \right) [\gcd(i, j) = d] \\ & = \sum_{d = 1}^n \sum_{i = 1}^{\left\lfloor\frac{n}{d}\right\rfloor} \sum_{j = 1}^{\left\lfloor\frac{m}{d}\right\rfloor} \varphi(ij) [\gcd(i, j) = 1] \\ & = \sum_{d = 1}^n \sum_{i = 1}^{\left\lfloor\frac{n}{d}\right\rfloor} \varphi(i) \sum_{j = 1}^{\left\lfloor\frac{m}{d}\right\rfloor} \varphi(j) [\gcd(i, j) = 1] \\ & = \sum_{d = 1}^n \sum_{k = 1}^{\left\lfloor\frac{n}{d}\right\rfloor} \mu(k) \sum_{i = 1}^{\left\lfloor\frac{n}{dk}\right\rfloor} \varphi(ik) \sum_{j = 1}^{\left\lfloor\frac{m}{dk}\right\rfloor} \varphi(jk) \\ & = \sum_{T = 1}^n \sum_{k\mid T} \mu(k) \sum_{i = 1}^{\left\lfloor\frac{n}{T}\right\rfloor} \varphi(ik) \sum_{j = 1}^{\left\lfloor\frac{m}{T}\right\rfloor} \varphi(jk) \end{aligned}

套路地设出来

f(k, n) = \sum_{i = 1}^n \varphi(ik)

那么

ans = \sum_{T = 1}^n \sum_{k\mid T} \mu(k) f\left(k, \left\lfloor\dfrac{n}{T}\right\rfloor \right) f\left(k, \left\lfloor\dfrac{m}{T}\right\rfloor \right)

又有递推式

f(k, n) = f(k, n - 1) + \varphi(nk)

即 f 可以在 \Theta(n\ln n) 时间内预处理。

但是这个 f 带一个 k，无法整除分块，只能暴力，所以查询是 \Omicron(T\sum\limits_{i = 1}^n \dfrac{n}{i}) \simeq \Omicron(T n\ln n) 的。

我们想要整除分块，那就弄个前缀和。

把整个表示出来

g(n, m, l) = \sum_{i = 1}^l \sum_{k\mid i} \mu(k) f(k, n) f(k, m)

那么整除分块大概长这样

g\left(\left\lfloor\dfrac{n}{l}\right\rfloor, \left\lfloor\dfrac{m}{l}\right\rfloor, r \right) - g\left(\left\lfloor\dfrac{n}{l}\right\rfloor, \left\lfloor\dfrac{m}{l}\right\rfloor, l - 1 \right)

同样有递推式

g(n, m, l) = g(n, m, l - 1) + \sum_{k\mid l} \mu(k) f(k, n) f(k, m)

预处理是

\Omicron\left(n \sum_{i = 1}^n \left(\sum_{j = 1}^{\frac{n}{i}} \dfrac{n}{j}\right) + \dfrac{n}{i} \right) \simeq \Omicron(n^3)

会 \rm TLE + MLE。

但是它能够做到十分优秀的 \Omicron(T \sqrt{n}) 回答。

如果要将两种方法结合，那么就是大家喜闻乐见的 根号分治 了。

（其实题目背景已经有提示了）

A:“数论,分块。”

设 k 为阈值，表示预处理 g(n, m, l) 时 n, m 只处理到 k。

那么计算时对于 l \le \left\lfloor\dfrac{n}{k}\right\rfloor 的直接暴力；对于 l > \left\lfloor\dfrac{n}{k}\right\rfloor 的部分，有 \left\lfloor\dfrac{n}{l}\right\rfloor \le k，直接用预处理过的 g。

Code

//18 = 9 + 9 = 18.
#include <iostream>
#include <cstdio>
#include <vector> 
#define Debug(x) cout << #x << "=" << x << endl
typedef long long ll;
using namespace std;

const int MAXN = 5e4 + 5;
const int N = 5e4;
const int MAXK = 155;
const int K = 150;
const int MOD = 23333;
typedef int arr[MAXN];
int add(int a, int b) {return (a + b) % MOD;}
int sub(int a, int b) {return (a - b + MOD) % MOD;}
int mul(int a, int b) {return (ll)a * b % MOD;}

arr p, mu, phi;
bool vis[MAXN];
vector<int> f[MAXN], g[MAXK][MAXK];

void pre()
{
    mu[1] = phi[1] = 1;
    for (int i = 2; i <= N; i++)
    {
        if (!vis[i])
        {
            p[++p[0]] = i;
            mu[i] = MOD - 1;
            phi[i] = (i - 1) % MOD;
        }
        for (int j = 1; j <= p[0] && i * p[j] <= N; j++)
        {
            vis[i * p[j]] = true;
            if (i % p[j] == 0)
            {
                mu[i * p[j]] = 0;
                phi[i * p[j]] = mul(phi[i], p[j]);
                break;
            }
            mu[i * p[j]] = mul(mu[i], mu[p[j]]);
            phi[i * p[j]] = mul(phi[i], phi[p[j]]);
        }
    }

    for (int k = 1; k <= N; k++)
    {
        f[k].resize(N / k + 5);
        for (int n = 1; n <= N / k; n++)
        {
            f[k][n] = add(f[k][n - 1], phi[n * k]);
        }
    }

    for (int n = 1; n <= K; n++)
    {
        for (int m = n; m <= K; m++)
        {
            g[n][m].resize(N / m + 5);
            for (int i = 1; i <= N / m; i++)
            {
                int wjy = mul(mu[i], mul(f[i][n], f[i][m]));
                for (int j = 1; j <= N / m / i; j++)
                {
                    g[n][m][i * j] = add(g[n][m][i * j], wjy);
                }
            }
            for (int l = 1; l <= N / m; l++)
            {
                g[n][m][l] = add(g[n][m][l], g[n][m][l - 1]);
            }
        }
    }
}

int block(int n, int m)
{
    if (n > m)
    {
        swap(n, m);
    }
    int res = 0, xsy = m / K;
    for (int i = 1; i <= xsy; i++)
    {
        for (int j = 1; j <= xsy / i; j++)
        {
            int t = i * j;
            res = add(res, mul(mu[i], mul(f[i][n / t], f[i][m / t])));
        }
    }
    for (int l = xsy + 1, r; l <= n; l = r + 1)
    {
        int k1 = n / l, k2 = m / l;
        r = min(n / k1, m / k2);
        res = add(res, sub(g[k1][k2][r], g[k1][k2][l - 1]));
    }
    return res;
}

int main()
{
    pre();
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n, m;
        scanf("%d%d", &n, &m);
        printf("%d\n", block(n, m));
    }
    return 0;
}