abc254

abc254

D - Together Square

题目描述

给定一个$N$， 找到满足$1 \leq i, j \leq N, i \times j 是一个平方数$的有序二元组$(i, j)$的数量

数据范围

$1 \leq N \leq 10^5$

题解

看起来是一道很简单的题， 但是我当时没有想到

设$f(x)$是$x$的最大平方数因子， 即$f(x) = max_y \{ y | x, y是平方数 \}$， 那么$i \times j$是一个平方数等价于$\frac{i \times j}{f(i) \times f(j)}$是一个平方数(这是显然的)

此外根据定义， 如果把$\frac{i}{f(i)}$质因数分解， 每个质因数必然最多出现一次， 这里我们简单证明一下

如果有一个质因子$p$出现了两次或两次以上， 那么$f(i)$就不是最大的了， 因为存在$f(i) \times p^2$满足平方数因子的条件， 且比$f(i)$大

我们将$\frac{i \times j}{f(i) \times f(j)}$改写成$\frac{i}{f(i)} \times \frac{j}{f(j)}$， 这样的话， 当且仅当$\frac{i}{f(i)} = \frac{j}{f(j)}$时， $\frac{i \times j}{f(i) \times f(j)}$是一个平方数， 从而得到$i \times j$是一个平方数

所以我们只需要对每一个$1 \leq x \leq N$求出$f(x)$， 最后统计$\frac{x}{f(x)}$的个数就可以计算出答案

---

当然以上是官方的题解的说法， 我们如果自己想的话， 首先应该想到$i \times j$是一个平方数的话， $i \times j$的质因数分解中每个质因子必然出现了偶数次

也就是说$i$的质因子分解中出现次数为奇数的质因子， 在$j$的质因子分解中必然也出现了奇数次， 反之亦然

然后就同题解的思路了

代码

我们首先计算出$N$中所有的平方数并标记， 时间复杂度$O(\sqrt n)$

然后求出每个数的所有因子并找到$f(x)$， 时间复杂度$O(\sum_{i = 1}^{N} \frac{N}{i}) = O(N \ln n)$

最后统计答案$O(N)$

#include <iostream>
#include <cstdio>
#include <vector>

int n;
int ans;

int main()
{
    scanf("%d", &n);

    std:: vector<bool> sq(n + 1, 0); // 用于标记平方数
    std:: vector<int> cnt(n + 1, 0); // 存放i \ f(i) 的个数， 用于统计答案
    std:: vector<std:: vector<int> > f(n + 1); // 用于存放每个数的因子

    for(int i = 1; i * i <= n; i ++) sq[i * i] = true; //标记平方数

    for(int i = 1; i <= n; i ++)
        for(int j = i; j <= n; j += i)
            f[j].push_back(i); // 存放因子

    for(int i = 1; i <= n; i ++)
    {
        int mx = 0;

        for(int j = 0; j < f[i].size(); j ++)
            if(sq[f[i][j]])
                mx = f[i][j]; // 找最大的

        cnt[i / mx] ++;
    }

    for(int i = 1; i <= n; i ++) ans += cnt[i] * cnt[i]; // 计算答案

    printf("%d\n", ans);

    return 0;
}