题解：P12334 注视

prh_rpjiajia · 2025-04-26 09:02:30 · 题解

uqd：：04-26 09:26 首次发出\ uqd：：04-26 18:43 添加充分性证明\ uqd：：05-01 22:21 修改充分性证明\ uqd：：05-24 19:01 回答了问题

场切思路

定义 \operatorname{sd} 函数，表示一个数的各数位之和。

必要条件：因为对于正整数 x 有

\sum{\operatorname{sd}\left(x^{\smash{2}}\right)}\equiv \left(\sum \operatorname{sd}(x)\right)^2 \pmod{9}

, 很显然 \sum \operatorname{sd}(x^2) \leq \left( \sum \operatorname{sd}(x) \right)^2。

令 d = \sum \operatorname{sd}(x),S = \sum \operatorname{sd}(x^2) = y，则

d^2 \geq y, \quad d^2 \equiv y \pmod{9}

。

反之，只要找出最小的 d \geq \lceil \sqrt{y} \rceil, 满足 \quad d^2 \equiv y \pmod{9}，若 y \bmod 9 \notin \{0,1,4,7\}, 输出 -1。

否则只需从 d_0 = \lceil \sqrt{y} \rceil 开始，枚举至多 9 个 d，找到最小的 d 满足 d^2 \equiv y \pmod{9}。

代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll y;
int main(){
    cin>>y;
    if(y==0){
        cout<<0;
        return 0;
    }
    int r=y%9;
    if(r<0) r+=9;
    if(r!=0&&r!=1&&r!=4&&r!=7){
        cout<<-1;
        return 0;
    }
    ll d0 = (ll)ceil(sqrt((long double)y));
    for(ll d=d0;d<d0+9;d++){
        if(d*d>=y && (d*d-y)%9==0){
            cout<<d;
            return 0;
        }
    }
    cout<<-1;
    return 0;
}

充分性证明

1. 数字和与模 9 的同余性质

对于任意正整数 x，有：

设 d = \operatorname{sd}(x)，y = \operatorname{sd}(x^2)，则必然满足：

d^2 \equiv y \pmod{9} \quad \text{(必要条件)}

2. 数字和的不等式约束

由于平方运算不增加数字和（逐位平方和 \leq 和的平方）：

\operatorname{sd}(x^2) \leq (\operatorname{sd}(x))^2 \implies y \leq d^2

3. 存在性构造

对任意满足 d^2 \equiv y \pmod{9} 且 d^2 \geq y 的 d，构造 x 如下：

情况1：y = d^2

构造：取 x = \underbrace{11\cdots1}_{d\text{个}}。
验证：
- 当 d \leq 9 时，x^2 = \underbrace{12\cdots321}_{\text{对称数}}，直接计算得 \operatorname{sd}(x^2) = d^2。
- 当 d > 9 时，需调整构造（见下文）。

情况2：y < d^2 且 d^2 - y = 9k

构造：
1. 取基础数 x' = \underbrace{11\cdots1}_{d\text{个}}（保证 \operatorname{sd}(x') = d）。
2. 通过替换部分数字为 0 或其他数字，使得 \operatorname{sd}(x'^2) 减少 9k：
  - 每将一个 1 替换为 0，\operatorname{sd}(x') 减少 1，但 \operatorname{sd}(x'^2) 减少 9（因 1110^2 - 1111^2 的数字和差为 9 的倍数）。
  - 重复替换 k 次即可满足 \operatorname{sd}(x^2) = y。

构造的普适性

模 9 匹配：由 d^2 \equiv y \pmod{9}，差值 d^2 - y 必为 9 的倍数，故总能通过上述调整实现。
下界控制：因 d \geq \lceil \sqrt{y} \rceil，确保 d^2 \geq y 恒成立。

4. 最小性保证

从 d_0 = \lceil \sqrt{y} \rceil 开始枚举，首个满足 d^2 \equiv y \pmod{9} 的 d 即为最小解，因：

模 9 的周期为 9，只需检查 d_0 至 d_0 + 8。
若不存在，则 y \bmod 9 \notin \{0,1,4,7\}，无解。

结论

对任意 y \geq 0，若存在 d 满足：

则必存在正整数 x 使得 \sum \operatorname{sd}(x^2) = y 且 \sum \operatorname{sd}(x) = d。解法的充分性得证。

回答一些问题

问题1

有人问：平方运算不增加数字和，为什么qwq？

回顾数字和的定义：\ 对于一个正整数 x，其数字和 \operatorname{sd}(x) 定义为它的十进制表示中各位数字的总和：

\operatorname{sd}(x) = \sum_{i=0}^{n} d_i$ 其中 $ x = \sum_{i=0}^{n} d_i \cdot 10^i

我们需要证明对于任意正整数 x：

\operatorname{sd}(x^2) \leq (\operatorname{sd}(x))^2

数字和具有以下重要性质：

\operatorname{sd}(x) \leq 9 \cdot \text{位数}(x)

考虑 x 的各位数字 d_0, d_1, ..., d_n：

x = \sum_{i=0}^{n} d_i \cdot 10^i

平方后：

x^2 = \left( \sum_{i=0}^{n} d_i \cdot 10^i \right)^2 = \sum_{i=0}^{n} \sum_{j=0}^{n} d_i d_j \cdot 10^{i+j}

数字和 \operatorname{sd}(x^2) 是这个展开式中各项的数字和之和。关键观察：

进位效应：当 i+j \geq 1 时，10^{i+j} 会产生进位，使得高位的数字和"压缩"
交叉项：交叉项 2d_i d_j 会被进位分散到不同数位

比较两种计算方式：

直接平方和：(\sum d_i)^2 = \sum d_i^2 + 2\sum_{i<j} d_i d_j
平方后数字和：\operatorname{sd}(x^2) 是考虑了所有进位后的结果

由于进位会使得：

\operatorname{sd}(d_i d_j \cdot 10^{i+j}) \leq d_i d_j

因此整体有：

\operatorname{sd}(x^2) \leq \sum_{i,j} d_i d_j = (\sum d_i)^2

结论：\ 由于平方运算中的进位效应会"压缩"数字和，因此总有：

\operatorname{sd}(x^2) \leq (\operatorname{sd}(x))^2

当且仅当 x 的各位数字乘积不产生进位时（如全为 1 的数字），等号成立。

后记

感谢@cmrhhh和@yyyhy对此题解进行的问题指出，有不懂的或者有哪里我讲的不明白、不对的欢迎在评论区指出。

我之后可能还会对此题解进行修改，辛苦管理员。