[ABC254D] Together Square 题解

题目链接：[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;
}

---

参考文献：

[1] https://www.cnblogs.com/CDOI-24374/p/16807362.html

[2] https://www.cnblogs.com/tsawke/p/17032751.html