洛谷P4466 [国家集训队] 和与积题解

题意：

给出 $n$，统计满足下面条件的数对 $(a,b)$ 的个数：

$1\le a<b \le n$。

$a+b$ 整除 $a\times b$ ，即 $(a + b) \mid ab$。

输入格式：

一行一个整数数 $n$。

输出格式：

一行一个整数表示答案。

数据范围：

$1 \le n < 2^{31}$ 。

设 $d=\gcd(a,b)$ ，记 $a=xd,~b=yd$ ，则

$\frac{xyd}{x + y} \in \mathbb{N} \quad \texttt{且}\quad \gcd(x,y)=1$

由 $\gcd(x,y)=1$ 可知 $\gcd(y, x + y)=1$ ，则 $\gcd(xy, x + y)=1$ 。

再由 $\frac{xyd}{x + y} \in \mathbb{N}$ 可知 $(x + y) \mid d$ ，显然 $x + y \le d$ 。

又因为 $xd \le n, yd \le n$ 且 $x < y$ ，所以 $d \le \left\lfloor \frac{n}{y}\right \rfloor$ 。

那么答案就是下式：

$\begin{aligned} \mathrm{Ans} &= \sum_{x=1}^{\sqrt{n}} \sum_{y=x+1}^{\sqrt{n}}\left\lfloor\frac{\left\lfloor\frac{n}{y}\right\rfloor}{x+y}\right\rfloor[\gcd(x, y)=1] \\[6pt]&=\sum_{d=1}^{\sqrt{n}}\mu(d)\sum_{x=1}^{\sqrt{n}} \sum_{y=x+1}^{\sqrt{n}}\left\lfloor\frac{\left\lfloor\frac{n}{y}\right\rfloor}{x+y}\right\rfloor[d \mid x][d \mid y] \\[6pt]&=\sum_{d=1}^{\sqrt{n}}\mu(d)\sum_{x=1}^{\left\lfloor\frac{\sqrt{n}}{d}\right\rfloor} \sum_{y=x+1}^{\left\lfloor\frac{\sqrt{n}}{d}\right\rfloor}\left\lfloor\frac{\left\lfloor\frac{n}{yd^2}\right\rfloor}{x+y}\right\rfloor \end{aligned}$

令 $s = x+y$ ，则

$\mathrm{Ans} = \sum_{d=1}^{\sqrt{n}}\mu(d)\sum_{y=2}^{\left\lfloor\frac{\sqrt{n}}{d}\right\rfloor} \sum_{s=y+1}^{2y-1}\left\lfloor\frac{\left\lfloor\frac{n}{yd^2}\right\rfloor}{s}\right\rfloor$

虽然这个式子非常毒瘤，但是仔细看看又确实可以数论分块。

来分析一下复杂度：

记

$S(n,k) = \sum_{i=2}^n\sum_{s=i+1}^{2i-1}\left\lfloor\frac{k}{is}\right\rfloor$

直接算就是

$\sum_{i=2}^n\mathcal{O}\left(\sqrt{\frac{k}{i}}\right) = \mathcal{O}(\sqrt{nk})$

提示：这里用到了 link 中提到的公式

因为

$\mathrm{Ans} = \sum_{k=1}^{\sqrt{n}} \mu(k) S\left(\left\lfloor\frac{\sqrt{n}}{k}\right\rfloor,\left\lfloor\frac{n}{k^2}\right\rfloor\right)$

所以复杂度是

$\begin{aligned} \sum_{k=1}^{\sqrt{n}} \mathcal{O}\left(n^{\frac{3}{4}} k^{-\frac{3}{2}}\right) &= \mathcal{O}(n^{\frac{3}{4}})\mathcal{O}\left(\int_1^{\sqrt{n}} k^{-\frac{3}{2}} \mathrm{d}k\right) \\[6pt]&=\mathcal{O}(n^{\frac{3}{4}})\mathcal{O}\left(\left.-\frac{2}{\sqrt{k}}\right|_1^{\sqrt{n}}\right) \end{aligned}$

后面的东西就是

$\left.-\frac{2}{\sqrt{k}}\right|_1^{\sqrt{n}} =\left(-\frac{2}{n^{\frac{1}{4}}}\right)-\left(-\frac{2}{\sqrt{1}}\right) =2-\frac{2}{n^{\frac{1}{4}}}$

因为 $n \ge 1$ ，所以这个东西不会超过 $2$ 。

因此时间复杂度为 $\mathcal{O}(n^{\frac{3}{4}})$ 。

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(5e5 + 15))

char ck[N];
int cnt, mu[N], pri[N]; ll res;
void Mobius(int n)
{
    mu[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        if(!ck[i]) { pri[++cnt] = i, mu[i] = -1; }
        for(int j = 1; j <= cnt && pri[j] * i <= n; j++)
        {
            int pos = pri[j] * i; ck[pos] = 1;
            if(i % pri[j]) { mu[pos] = -mu[i]; } else break;
        }
    }
}
int calc(int s, int k)
{
    int sum = 0;
    for(int l = s + 1, r; l < 2 * s; l = r + 1)
    {
        if(!(k / l)) return sum;
        r = min(k / (k / l), 2 * s - 1);
        sum += (r - l + 1) * (k / l);
    }
    return sum;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n; int sqn = sqrt(n); Mobius(sqn);
    for(int i = 1; i <= sqn; i++)
        if(mu[i] != 0) {
            for(int j = 1; j <= sqn / i; j++)
                res += mu[i] * calc(j, n / (i * i * j));
        }
    cout << res << '\n';
    return 0;
}