[ABC254D] Together Square 题解

题意：

给定 $n$，求满足以下条件的二元组 $(i, j)$ 数量：$1 \le i, j \le n, i \times j = k^2(k \in \mathbb{N}^*)$。

$1 \le n \le 2 \times 10^5$

先来讲讲常规做法：

记 $f_i$ 为 $i$ 最大的完全平方数因子，然后我们可以得到这样一个式子

$i \times j=f_i \times \frac{i}{f_i} \times f_j \times \frac{j}{f_j}$

整理一下可得

$\frac{i}{f_i}=\frac{j}{f_j}$

统计一下 $\frac{i}{f_i}$ 即可。时间复杂度 $\mathcal{O}(n \sqrt{n})$ 或者用筛法可以到 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
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)(2e5 + 15))

int vis[N];
int f(int x)
{
    int res = 0;
    for(int i = 1; i * i <= x; i++)
        if(x % i == 0) {
            int j = x / i, a = sqrt(i), b = sqrt(j);
            if(a * a == i) up(res, i); if(b * b == j) up(res, j);
        }
    return res;
}
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, res = 0; cin >> n;
    for(int i = 1; i <= n; i++) ++vis[i / f(i)];
    for(int i = 1; i <= n; i++) res += vis[i / f(i)];
    cout << res << '\n';
    return 0;
}

然后来讲讲更快的 $\mathcal{O}(\sqrt{n})$ 的解法。

考虑讲题目要枚举的 $i,j$ 拆成 $i=a^2\times c,~j = b^2\times c$ ，暂且仅考虑 $i < j$

由 $i < j < n$ 得

$a^2 < b^2 < \frac{n}{c}$

即

$a<b<\sqrt{\frac{n}{c}}$

对于确定的 $a,b$ ，显然有 $1 \le c \le \frac{n}{b^2}$ ，于是它的贡献似乎是 $\left\lfloor\frac{n}{b^2}\right\rfloor$ 。

事实上，如果 $a,b$ 不互质，则显然会被 $a^{\prime} = \frac{a}{\gcd(a,b)}$ 的枚举包含，因此贡献是

$\left\lfloor\frac{n}{b^2}\right\rfloor \times[\operatorname{gcd}(a, b)=1]$

这个互质真是非常巧妙，以至于刚好满足了 $\varphi(b)$ 的定义。

于是我们只需要枚举 $i(i^2 \le n)$ ，每次加上 $\varphi(i)\times \left\lfloor\frac{n}{i^2}\right\rfloor$ 即可。

时间复杂度 $\mathcal{O}(\sqrt{n})$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
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)(2e6 + 15))

int L,phi[N]; char ck[N]; vector<int> P;
void Euler(int n)
{
    ck[1] = true; phi[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        if(!ck[i]) { P.push_back(i); phi[i] = i - 1; }
        for(auto p : P) {
            int pos = i * p; ck[pos] = 1;
            if(i % p) { phi[pos] = phi[i] * phi[p]; }
            else { phi[pos] = phi[i] * p; break; }
        }
    }
}
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, res = 0; cin >> n; L = sqrt(n); Euler(L + 5);
    for(int i = 1; i * i <= n; i++) res += phi[i] * (n / (i * i));
    cout << (res * 2 - n) << '\n';
    return 0;
}