当前位置：首页 > news >正文

蓝桥杯 2024 15届国赛 A组儿童节快乐

news 2025/6/12 16:31:12

P10576 [蓝桥杯 2024 国 A] 儿童节快乐

题目描述

五彩斑斓的气球在蓝天下悠然飘荡，轻快的音乐在耳边持续回荡，小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下，六一来了。

今天是六一儿童节，小蓝老师为了让大家在节日里享受解题的乐趣，特地准备了一道有趣的题目。

题目内容为：求出所有满足以下条件的整数 $n$ 的总和：

$(n + 10120300500)$ 是一个完全平方数。
$(n - 10120300500)$ 也是一个完全平方数。

一个数如果可以表示为另一个整数的平方，那么这个数就叫做完全平方数。例如， $4$ 可以表示为 $2$ 的平方， $9$ 可以表示为 $3$ 的平方，因此 $4$ 和 $9$ 都是完全平方数。

请大家用心仔细地思考，求出答案。同时祝大家儿童节快乐，解题过程开心顺遂！

输入格式

这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

输出格式

这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

题解

本题官方判题机有误，真实答案已经超过 longlong 范围，请使用洛谷判题机
思路
- 设 $k = 10120300500$
- 容易想到从 $1$ 开始枚举 $n$ ，看看有多少个 $n$ 满足这样的条件，并累计，但经过测试，即使枚举到 $10^9$ ，枚举到 $10^{10}$ 还是有新的 $n$ 满足条件，因此边界无法确定
- 观察题目所给的两个式子
  $a^2 \tag{1}$
  
  $b^2 \tag{2}$
  - 可以看出， $1) - (2) = a^2 -b^2 = 2k$
  - 由平方差公式可得： $(a + b) (a - b) = 2 k$
  - 若能求解出 $a, b$ 即可求出 $n$ ， $a^2 - k = b^2 + k = \frac{a^2 + b^2}{2}$
- 如何求解 $a, b$ ？
  - 设 $x = (a + b), y = (a - b)$ ，那么有 $\times y = 2k$
  - 枚举 $2 k$ 的所有因子，即可求出 $x, y$
    - $2k = 20240601000 > 10^{10}$ ，需要使用 $O(\sqrt n)$ 算法枚举因子
  - 求出 $x, y$ ，那么 $\frac{x+y}{2}, b = \frac{x-y}{2}$
- longlong 能存下答案和中间结果吗？
  - 极端一些，假设 $x = k - 1, y = 1$ ，那么 $\approx k/2 \approx 5 \times 10^9$
  - 当计算 $n$ 时， $a^2 + b^2 \approx 5 \times 10^{19}$ ，longlong 的范围大概是 $\times 10^{18}$ ，存储不了
  - 直接用 __int128 一步到位，输出要自定义
- 至此，可以写出代码
```
typedef __int128 Int;
int main() {Int k = 10120300500;Int s = 2 * k;Int res = 0;for(Int x = 1; x * x <= s; ++x) {if(s % x == 0) {Int y = s / x;Int a = (x + y) / 2, b = (x - y) / 2;res += (a * a + b * b) / 2;}}return 0;
}
```
- 但是提交后发现出错了，为什么呢？
  - 观察到求解 $a, b$ 时，使用了除法，而 cpp 的除法是向零截断的，因此可能存在小数 $a, b$ 也满足条件，那么求出的 $n$ 也是一个小数，与题目要求整数不符
  - 要保证 $a, b$ 是整除得到的，那么 $x + y, x - y$ 必须是偶数

AC 代码

#include <bits/stdc++.h>
using namespace std;typedef __int128 Int;void output(Int num) {char buf[50] = {0};int i = 0;while(num) {buf[i++] = '0' + num % 10;num /= 10;}for(int j=i-1; j>=0; --j) cout << buf[j];
}int main() {Int k = 10120300500;Int s = 2 * k;Int res = 0;for(Int x = 1; x * x <= s; ++x) {if(s % x == 0) {Int y = s / x;if((x + y) % 2 == 0 && (x - y) % 2 == 0) {Int a = (x + y) / 2, b = (x - y) / 2;res += (a * a + b * b) / 2;}}}output(res);return 0;
}