洛谷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;
}