自动搬运

查看原文

来自洛谷，原作者为

	prh_rpjiajia 万语难尽涩于口 祈尔繁芜胜常春

搬运于2025-08-24 23:14:42，当前版本为作者最后更新于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$，有：

• $\operatorname{sd}(x) \equiv x \pmod{9}$，
• $\operatorname{sd}(x^2) \equiv x^2 \pmod{9} \equiv (\operatorname{sd}(x))^2 \pmod{9}$。

设 $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$ 满足：

1. $d^2 \geq y$，
2. $d^2 \equiv y \pmod{9}$，

则必存在正整数 $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)$
• $\operatorname{sd}(x) \equiv x \pmod{9}$（数字根性质）

考虑 $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)$ 是这个展开式中各项的数字和之和。关键观察：

1. 进位效应：当 $i+j \geq 1$ 时，$10^{i+j}$ 会产生进位，使得高位的数字和"压缩"
2. 交叉项：交叉项 $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$ 的数字），等号成立。

后记

感谢

yyyhy](https://www.luogu.com.cn/user/307542)对此题解进行的问题指出，有不懂的或者有哪里我讲的不明白、不对的欢迎在评论区指出。

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