luoguP4466 [国家集训队]和与积

时间复杂度到底是多少……

和与积

一眼望过去感觉像莫反，心里拔凉

但还是坚强的把25分的暴力打了，不出意外，刚刚好25分，于是，找规律

打了个表找规律，看见答案一块一块的贼像数论分块，心里更凉了，把100以内的数对打表出来，发现（反正我看见的） $gcd(a, b) \ne 1$ ，硬着头皮推

莫反
$$
\begin{aligned}
设 & gcd(a, b) = r, c = \frac{a}{r}, d = \frac{b}{r}, k \in \mathbb{N_+} \\
& a b = (a + b) k \\
& r^2 c d = r (c + d) k \\
& r c d = (c + d) k \\
\because & gcd(c, d) = 1 \\
\therefore & cd \mid k \\
设 & k’ = \frac{k}{cd} \\
有 & r = (c + d) k’
\end{aligned}
$$
乱推一波到这里不知道该干啥了，于是去看了看（被我遗忘了很久的）莫反，想到莫反的经典操作——将枚举约数改成枚举倍数

考虑求 $c, d, k’, (c < d, gcd(c, d) = 1, k’ \in \mathbb{N_+})$ ，则可计计算出 $r = (c + d) k’, a = rc, b = rd$ ，又因为 $b \le n$ ，所以 $d (c + d) k’ \le n$ ，也就是说， $c, d$ 确定以后， $k’$ 的范围也确定了，可以直接计算有几对，时间复杂度为 $O(n^2)$ ——woc，暴力也是 $O(n^2)$ 啊！

再次推式子：
$$
\begin{aligned}
Ans
& = \sum_{i = 1}^N \sum_{j = 1}^{i - 1} [gcd(i, j) == 1] \lfloor \frac{N}{i (i + j)} \rfloor \\
& = \sum_{i = 1}^N \sum_{j = 1}^{i - 1} \sum_{k | gcd(i, j)} \mu(k) \lfloor \frac{N}{i (i + j)} \rfloor \\
& 令 pk = i, qk = j, N’k = N, 有 : \\
Ans
& = \sum_{k = 1}^N \sum_{p = 1}^N’ \sum_{q = 1}^{p - 1} \mu(k) \lfloor \frac{N’}{p (p + q)} \rfloor \\
\end{aligned}
$$
到这一步动不了了，主要是 $p(p + q)$ 是个二次项没法整除分块，卡了1145141919810h，高素质的瞟了一眼题解：
$$
\begin{aligned}
Ans
& = \sum_{k = 1}^N \sum_{p = 1}^N’ \sum_{q = 1}^{p - 1} \mu(k) \lfloor \frac{N’}{p (p + q)} \rfloor \\
& = \sum_{k = 1}^N \sum_{p = 1}^N’ \sum_{q = 1}^{p - 1} \mu(k) \lfloor \frac{\lfloor \frac{N’}{p} \rfloor}{p + q} \rfloor \\
\end{aligned}
$$
于是当 $k, p$ 定了后，后面只关于 $q$ 可以整除分块（我咋就想不到呢？）

机房的巨佬在这一步就可以做了，但蒟蒻我还是不能理解（感觉三个 $\sum$ 时间不是更慢了吗），所以我又绕了一下

发现这里没有必要跑满每一个 $N$ ，中间有一步：
$$
Ans = \sum_{i = 1}^N \sum_{j = 1}^{i - 1} \sum_{k | gcd(i, j)} \mu(k) \lfloor \frac{N}{i (i + j)} \rfloor \\
$$
这里当 $i \ge \sqrt{N}$ 时后面就为 $0$ ，所以直接令 $M = \sqrt{N}$ ，则
$$
Ans = \sum_{k = 1}^M \sum_{p = 1}^M’ \sum_{q = 1}^{p - 1} \mu(k) \lfloor \frac{\lfloor \frac{M’}{p} \rfloor}{p + q} \rfloor \\
$$
枚举 $k$ 用 $N^{\frac{1}{2}}$ ，枚举 $p$ 用大概用个 $N^{\frac{1}{4}}$ ，数论分块大概用个 $\sqrt{N^{\frac{1}{4}}}$ ……？？？啊啊啊算不出来了

看了一下题解，大家也都各不相同，但好像是 $O(n^{\frac{3}{4}})$ ？

#include <bits/stdc++.h>
#define LL long long
#define STC static
using namespace std;
const int N = 1e5 + 5;
int mu[N];
vector<int> prime;
void prev(int n)
{
    STC int v[N];
    mu[1] = 1;
    for (int i = 2; i <= n; ++i)
    {
        if (!v[i])
            prime.push_back(i), mu[i] = -1;
        for (int j : prime)
        {
            if (i * j > n)
                break;
            v[i * j] = true;
            if (i % j)
                mu[i * j] = -mu[i];
            else
                break;
        }
    }
}
LL work(int p, int x)
{
    if (!x)
        return 0;
    LL res = 0;
    int ed = p << 1;
    for (int l = p + 1, r; l < ed; l = r + 1)
    {
        if (x / l)
            r = min(x / (x / l), ed - 1);
        else
            return res;
        res += (LL)(r - l + 1) * (x / l);
    }
    return res;
}
int main()
{
    int n, m;
    LL ans = 0;
    scanf("%d", &n);
    m = sqrt(n);
    prev(m);
    for (int i = 1; i <= m; ++i)
    {
        if (!mu[i])
            continue;
        for (int j = 1; j * i <= m; ++j)
            ans += work(j, n / (i * i * j)) * mu[i];
    }
    printf("%lld\n", ans);
    return 0;
}

感觉自己莫反好弱