NekoNowcoder

Appearance

FakeNews - 题解 ​

标签与难度 ​

标签: 数学, 数论, 规律题, O(1)

难度: 1200

题目大意喵~ ​

你好呀，未来的算法大师！我是你们的我小助教，喵~ 让我们一起来看看这道有趣的题目吧！

题目是这样的：有一个自称很懂数学的大人物宣称，从1到n的平方和（也就是 12+22+⋯+n21^2 + 2^2 + \dots + n^2）永远不可能是另一个整数的平方。我们要做的就是当一名“记者”，戳穿他的“Fake news!”。

简单来说，就是给我们一个正整数 nn，我们需要判断 ∑k=1nk2\sum_{k=1}^{n} k^2 是否是一个完全平方数。

  • 输入: 会有多组测试数据。每组数据给出一个整数 nn。
  • 输出: 如果那个和是完全平方数，我们就输出 "Fake news!"，表示大人物说错了。如果不是，我们就输出 "Nobody knows it better than me!"，表示他这次说对了。

举个栗子🌰：

  • 如果 n=1n=1, 那么和就是 12=11^2 = 1, 而 11 是 121^2，所以是完全平方数。
  • 如果 n=2n=2, 和是 12+22=51^2 + 2^2 = 5, 这可不是任何整数的平方哦。

解题思路分析 ​

喵~ 这个问题看起来很数学，但别担心，跟着我的猫爪印一步步来，你会发现它其实很可爱！

第一步：把问题变简单！ ​

首先，我们要计算那个长长的和：∑k=1nk2\sum_{k=1}^{n} k^2。每次都用循环去加肯定太慢啦，幸好聪明的数学家们早就为我们准备好了公式，的说！

平方和公式：

∑k=1nk2=12+22+⋯+n2=n(n+1)(2n+1)6\sum_{k=1}^{n} k^2 = 1^2 + 2^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}

有了这个公式，问题就变成了：判断 n(n+1)(2n+1)6\frac{n(n+1)(2n+1)}{6} 是不是一个完全平方数。

第二步：最直接的想法——暴力计算！ ​

最直观的思路就是，对于每个给定的 nn，我们直接套用公式计算出这个和 sum，然后判断 sum 是不是完全平方数。

怎么判断一个数 sum 是不是完全平方数呢？ 一个简单的方法是：

  1. 计算 sum 的平方根，long long root = sqrt(sum)。这里 sqrt 函数会返回一个浮点数，我们把它强制转换成整数，会去掉小数部分。
  2. 然后我们检查 root * root 是否等于 sum。如果相等，那 sum 就是一个完美的完全平方数啦！

这个方法在大多数情况下都是可行的，就像参考代码1那样。但是，作为一个追求极致的我，我总觉得还有更优雅的解法，喵~

第三步：寻找隐藏的规律！ ​

让我们来当一回侦探，测试一下前面几个 nn 的值，看看能不能发现什么线索，呐？

  • n = 1: 和 = 1×2×36=1=12\frac{1 \times 2 \times 3}{6} = 1 = 1^2。是完全平方数！ (Fake news!)
  • n = 2: 和 = 2×3×56=5\frac{2 \times 3 \times 5}{6} = 5。不是。
  • n = 3: 和 = 3×4×76=14\frac{3 \times 4 \times 7}{6} = 14。不是。
  • n = 4: 和 = 4×5×96=30\frac{4 \times 5 \times 9}{6} = 30。不是。
  • ... (我们继续往下找) ...
  • ... (找呀找呀找朋友) ...
  • n = 24: 和 = 24×25×496=4×25×49=4900=702\frac{24 \times 25 \times 49}{6} = 4 \times 25 \times 49 = 4900 = 70^2。是完全平方数！ (Fake news!)

我们发现了两个让大人物被打脸的例子：n=1n=1 和 n=24n=24。

这时候，一个大胆的猜想就浮现在了我的猫猫脑海里：会不会...只有这两个解呢？

第四步：揭开谜底！ ​

这个猜想是正确的！这个问题在数学上被称为**“炮弹问题” (Cannonball Problem)**，因为它等价于问：需要多少个炮弹才能堆成一个正四角锥，并且这些炮弹又能恰好在地面上摆成一个正方形？

这是一个著名的数论问题，数学家们在很久以前就已经证明，除了平凡解 n=0n=0 之外，只有当 n=1n=1 和 n=24n=24 时，这个平方和才是一个完全平方数。

这个证明过程涉及到了椭圆曲线，对于我们算法竞赛来说有点太复杂了，喵~ 但我们可以心安理得地使用这个结论！

所以，这道题的最终解法就是： 判断输入的 n 是否等于 1 或者 24。

  • 如果是，就输出 "Fake news!"。
  • 如果不是，就输出 "Nobody knows it better than me!"。

这样一来，问题就变成了一个超级简单的判断题，时间复杂度瞬间降到了 O(1)O(1)，是不是超级厉害！这就是数学的魅力呀，喵~

代码实现 ​

下面就是我根据这个绝妙的思路，为你精心准备的代码啦！注释里有我的小心思哦~

cpp
#include <iostream>

// 使用快速 I/O，让我们的程序跑得像猫一样快，喵~
void fast_io() {
    // 关闭 C++ 标准流与 C 标准流的同步
    std::ios_base::sync_with_stdio(false);
    // 解除 cin 和 cout 的绑定
    std::cin.tie(NULL);
}

// 解决单个测试用例的函数
void solve() {
    long long n;
    std::cin >> n;

    // 根据我们发现的数学规律（炮弹问题）
    // 只有当 n=1 或 n=24 时, 1到n的平方和才是一个完全平方数
    if (n == 1 || n == 24) {
        std::cout << "Fake news!\n";
    } else {
        std::cout << "Nobody knows it better than me!\n";
    }
}

int main() {
    fast_io();

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析 ​

  • 时间复杂度: O(T)O(T) 对于每个测试用例，我们只进行了一次简单的 if-else 判断，这个操作是常数时间 O(1)O(1) 的。如果有 TT 个测试用例，总时间复杂度就是 O(T)O(T)，超级快！

  • 空间复杂度: O(1)O(1) 我们没有使用任何随输入规模 nn 变化的额外存储空间，只用了几个变量。所以空间复杂度是 O(1)O(1)，非常节省内存的说。

知识点总结 ​

通过这道题，我们学到了不少好东西呢，喵~

  1. 平方和公式: 这是一个非常基础且重要的求和公式，要记在小本本上哦！

    ∑k=1nk2=n(n+1)(2n+1)6 \sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}

  2. 完全平方数判断: 虽然我们最后没用上，但 long long root = sqrt(x); if (root * root == x) 是判断一个数是否为完全平方数的常用技巧。

  3. 竞赛中的规律探索: 面对看似复杂的计算题，先别急着硬算。可以尝试计算一些小数据，观察其结果，往往能发现意想不到的简单规律。这是一种非常重要的解题策略！

  4. 炮弹问题 (Cannonball Problem): 作为一个有趣的知识点，知道了这个问题的背景，不仅能让我们秒解此题，还能在小伙伴面前小秀一下知识储备，是不是很酷？

好啦，这次的题解就到这里啦！希望对你有帮助，喵~ 继续加油，你一定能成为最棒的算法大师！