Moe's CF Life

Appearance

D. Many Perfect Squares - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 844 (Div. 1 + Div. 2, based on VK Cup 2022 - Elimination Round) 标签: brute force, dp, math, number theory 难度: *1800

题目大意喵~ ​

主人你好呀！这道题是这样的说：

我们有一个包含 n 个不同正整数的集合 a。我们的任务是，找到一个非负整数 x（x 可以很大很大，到 10^18 都可以哦！），让 a_1 + x, a_2 + x, ..., a_n + x 这个新集合里，完美平方数的数量尽可能多。最后，我们只要告诉裁判这个最多的数量是多少就可以啦！

举个栗子，如果 a = {1, 6, 13, 22, 97}，当我们取 x = 3 时，新集合就变成了 {4, 9, 16, 25, 100}。哇！它们分别是 2^2, 3^2, 4^2, 5^2, 10^2，全都是完美平方数耶！所以对于这个例子，答案就是 5 啦，喵~

解题思路大揭秘！ ​

这道题看起来 x 的范围非常大，有 10^18 那么大，直接去枚举 x 肯定是不行的啦！那我们该怎么办呢？别急，让本喵带你一步步分析，喵~

关键的突破口：差分思想！ ​

我们不妨先考虑一个简化版的问题：如果我们希望 a_i + x 和 a_j + x 这两个数同时成为完美平方数，会发生什么呢？

假设：

  • a_i + x = p^2
  • a_j + x = q^2

这里 p 和 q 都是非负整数。把这两个式子相减，x 就被消掉啦！ (a_j + x) - (a_i + x) = q^2 - p^2a_j - a_i = q^2 - p^2

喵！看呐，这是一个平方差公式！ a_j - a_i = (q - p)(q + p)

这个发现太重要了！它告诉我们，两个数之差 a_j - a_i 必须能被分解成两个因数 (q - p) 和 (q + p) 的乘积。

从差分到求解 x ​

既然有了这个关系，我们就可以改变策略了！我们不再枚举 x，而是枚举数组 a 中的数对 (a_i, a_j)。

对于每一对 (a_i, a_j)（假设 i < j），我们计算出它们的差 diff = a_j - a_i。然后，我们来分解 diff：

  1. 我们找到 diff 的所有因数对 (u, v)，使得 u * v = diff。为了效率，我们只需要枚举 u 到 sqrt(diff) 即可，v 就是 diff / u。
  2. 我们令 u = q - p，v = q + p。
  3. 解这个二元一次方程组，可以得到：
    • q = (u + v) / 2
    • p = (v - u) / 2
  4. 为了让 p 和 q 是整数，(u + v) 和 (v - u) 都必须是偶数。这等价于 u 和 v 的奇偶性必须相同（要么都奇，要么都偶）。所以我们需要加一个判断 (u % 2) == (v % 2)。
  5. 得到 p 之后，我们就可以反推出 x 了！根据 a_i + x = p^2，我们有 x = p^2 - a_i。
  6. 题目要求 x >= 0，所以我们还需要保证 p^2 >= a_i。

通过这个过程，对于任意一对 (a_i, a_j)，我们都能找到所有可能让 a_i+x 和 a_j+x 同时成为平方数的 x。

如何统计最终答案？ ​

一个聪明的 x 可能会让很多个数都变成完美平方数。比如说，如果 x 让 k 个数 {a_{p_1}, a_{p_2}, ..., a_{p_k}} 都变成了完美平方数，那么我们任意从这 k 个数中选一对，比如 (a_{p_r}, a_{p_s})，按照上面的方法计算，都会得到同一个 x！

这也就是说，一个能产生 k 个完美平方数的 x，会被我们找到 C(k, 2) = k * (k - 1) / 2 次。

所以我们的完整策略是：

  1. 用一个 map<long long, int> x_counts 来记录每个候选 x 被找到了多少次。
  2. 遍历所有数对 (a_i, a_j)，按照上面的方法计算出所有可能的、合法的 x，并在 map 中给对应的 x 计数加一。
  3. 遍历完所有数对后，我们找到 map 中最大的计数值，记为 max_c。
  4. 现在我们有了 max_c = k * (k - 1) / 2，需要反解出 k。
    • 2 * max_c = k^2 - k
    • k^2 - k - 2 * max_c = 0
    • 使用求根公式，k = (1 + sqrt(1 + 8 * max_c)) / 2。（我们只取正根）
    • 只要 1 + 8 * max_c 是一个完全平方数，我们就能解出一个整数 k。这个 k 就是我们能得到的最大数量。
  5. 别忘了，答案至少是 1 嘛（总能让其中一个数变成平方数），所以我们的初始答案 max_ans 设为 1，然后用找到的 k 来更新它。

这样，我们就把一个看似无法下手的问题，转化成了一个可以通过枚举和计算解决的问题啦！是不是很巧妙的说？

代码实现喵~ ​

cpp
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <map>

void solve() {
    int n;
    std::cin >> n;
    std::vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    
    // 如果只有一个数，那答案肯定是1啦，喵~
    if (n == 1) {
        std::cout << 1 << "\n";
        return;
    }

    // 用一个 map 来统计每个可能的 x 被推导出了多少次
    std::map<long long, int> x_counts;

    // 遍历所有不同的数对 (a_i, a_j)
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            long long diff = a[j] - a[i]; // 这就是 q^2 - p^2 的值
            
            // 寻找 diff 的因子 u，v = diff / u
            // u = q - p, v = q + p
            for (long long u = 1; u * u <= diff; ++u) {
                if (diff % u == 0) {
                    long long v = diff / u;
                    
                    // 要想 p 和 q 是整数，u 和 v 的奇偶性必须相同
                    if ((u % 2) == (v % 2)) {
                        // 根据 u=q-p, v=q+p 解出 p
                        long long p = (v - u) / 2;
                        
                        // 我们需要找到 x 使得 a_i + x = p^2
                        // 所以 x = p^2 - a_i
                        long long p_squared = p * p;
                        
                        // 题目要求 x >= 0，所以 p^2 必须大于等于 a_i
                        if (p_squared >= a[i]) {
                            long long x = p_squared - a[i];
                            // 找到了一个合法的 x，给它计数+1
                            x_counts[x]++;
                        }
                    }
                }
            }
        }
    }

    // 答案至少是1
    int max_ans = 1;
    if (!x_counts.empty()) {
        int max_c = 0;
        // 找到被推导出次数最多的 x 的次数
        for (auto const& [x, count] : x_counts) {
            max_c = std::max(max_c, count);
        }

        // 如果一个 x 能产生 k 个完美平方数，它会被找到 C(k,2) = k*(k-1)/2 次
        // 我们现在有 max_c = k*(k-1)/2，需要反解出 k
        // 2*max_c = k^2 - k  =>  k^2 - k - 2*max_c = 0
        // k = (1 + sqrt(1 + 8*max_c)) / 2
        // 为了让 k 是整数，判别式 1 + 8*max_c 必须是完全平方数
        long long discriminant = 1 + 8LL * max_c;
        long long root = round(sqrtl(discriminant)); // 用 long double 提高精度
        
        if (root * root == discriminant) {
            // 如果判别式是完全平方数，我们就能解出整数 k
            int k = (1 + root) / 2;
            max_ans = std::max(max_ans, k);
        }
    }
    
    std::cout << max_ans << "\n";
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析 ​

  • 时间复杂度: O(N^2 * sqrt(A_max)) 的说。 我们有两层循环来遍历所有的数对 (a_i, a_j)，这是 O(N^2)。在内层，我们需要对差值 diff = a_j - a_i 进行因数分解，diff 最大可达 10^9 级别。分解因数的时间复杂度是 O(sqrt(diff))。所以总的时间复杂度就是 O(N^2 * sqrt(A_max))。对于这道题的数据范围 N <= 50，这是可以通过的哦！

  • 空间复杂度: O(N^2 * d(A_max)) 的说。 主要的空间开销是 x_counts 这个 map。在最坏的情况下，每个数对的每个因子对都可能产生一个不同的 x。d(A_max) 表示 A_max 的约数个数。虽然这是一个比较宽松的上界，但它说明了空间复杂度和 N^2 以及数的因子数量有关。在实际中，很多 x 会是重复的，所以 map 的大小会远小于理论上界，是完全可以接受的。

知识点与总结 ​

这道题真是一次有趣的冒险呢，喵~ 我们来总结一下这次冒险中学到的东西吧：

  1. 核心思想 - 差分与平方差：面对一个看似无从下手的变量 x，通过对两个目标状态（a_i+x=p^2, a_j+x=q^2）作差，成功消去了 x，将问题转化为了数论中的平方差分解问题。这是一种非常经典和有用的思想！

  2. 暴力枚举的艺术：虽然不能暴力枚举 x，但 N 很小，提示我们可以从已有的 N 个数入手。O(N^2) 的枚举数对是解决问题的关键。

  3. 组合计数反演：解题中最巧妙的一步，就是意识到 "一个能产生 k 个完美平方数的 x 会被找到 C(k, 2) 次"，并利用这个关系从计数值反推出真正的答案 k。这需要一点点组合数学的思维，很有趣对吧！

  4. 注意细节：比如 p 和 q 的整数条件（要求因子 u, v 同奇偶），以及 x >= 0 的约束，这些都是确保正确性的重要细节哦。

希望这篇题解能帮助到你，主人！要继续努力，享受解题的乐趣哦！喵~

Released under the MIT License.

Copyright © 2024-present Moe