UESTC CDOJ Lutece 1513 简单的数学题

Description

这是一道简单的数学题，简单到题目只给你一个正整数$N$，而你则输出一个$M$，这个$M$是由$N$的各个位数重新排列而来的（比如，$N=123$，则$M$可以为$123,213,321,312,132,231$）。由于$M$有许多许多，所以要求你输出一个满足$|N-M| \% 9 =0$ 的最小$M$。

$A \% 9 = 0$的含义为$A$是$9$的倍数，比如$9,18,0,9999$等。

Input

一个正整数$N(1<N<10^{1000})$，保证$N$的每一位都不是 0。

注意：因为$N$实在太大，请使用至少 1001 位的 char 数组，而非 int，保存$N$

Output

一个正整数$M$，如题目要求的那样。

Samples

输入数据 1

91

输出数据 1

19

Note

注意：因为 N 实在太大请使用至少 1001 位的 char 数组保存而非 int 保存 N

Resources

第八届 ACM 趣味程序设计竞赛第二场（正式赛）

分析

问题的核心在于约束条件 $|N - M| \% 9 = 0$。要理解这个条件，我们需要回顾一个经典的数论知识点：一个数能被 9 整除的充要条件是，这个数的各位数字之和能被 9 整除。

我们来简要证明一下：

任何一个正整数 $X$ 都可以写成各位数字的加权和形式。例如，$X = d_k d_{k-1} ... d_1 d_0$（其中 $d_i$ 是各位上的数字），可以表示为： $X = d_k * 10^k + d_{k-1} * 10^{k-1} + ... + d_1 * 10^1 + d_0 * 10^0$

我们知道 $10 ≡ 1 (\text{mod} 9)$，$100 = 10^2 ≡ 1^2 ≡ 1 (\text{mod} 9)$，以此类推，对于任何非负整数 $i$，都有 $10^i ≡ 1 (\text{mod} 9)$。

所以，对 $X$ 进行模 9 运算：

$X \% 9 ≡ (d_k * 10^k + ... + d_0 * 10^0) \% 9$

$X \% 9 ≡ (d_k * 1 + ... + d_0 * 1) \% 9$

$X \% 9 ≡ (d_k + d_{k-1} + ... + d_1 + d_0) \% 9$

这证明了 $X \% 9$ 等于 $(X 的各位数字之和) \% 9$。

现在我们回到约束条件 $|N - M| \% 9 = 0$。根据模运算的性质，$A \% 9 = 0$ 等价于 $A$ 是 9 的倍数。所以，$|N - M|$ 必须是 9 的倍数。

这又等价于 $(N - M)$ 是 9 的倍数，即 $(N - M) \% 9 = 0$。根据模运算的性质 $(A - B) \% C = ((A \% C) - (B \% C) + C) \% C$，我们可以推导出：$(N - M) \% 9 = 0$ 等价于 $N \% 9 = M \% 9$。

现在，我们利用上一节得到的结论：

• $N \% 9$ 等于 $(N 的各位数字之和) \% 9$。
• $M \% 9$ 等于 $(M 的各位数字之和) \% 9$。

所以，约束条件 $N \% 9 = M \% 9$ 就转化为了：$(N 的各位数字之和) \% 9 = (M 的各位数字之和) \% 9$

现在我们来考虑 $M$ 和 $N$ 的关系。题目规定 $M$ 是 $N$ 的一个排列。这意味着 $M$ 和 $N$ 拥有完全相同的数字集合，只是顺序不同，当然，他们的数字和也相同。

既然它们的数字和相等，那么它们对 9 取模的结果也必然相等。这意味着 $(N 的各位数字之和) \% 9 = (M 的各位数字之和) \% 9$ 这个条件对于任何由 $N$ 的数字排列而成的 $M$ 都是恒成立的。

所以问题被大大简化，变成了：给定一个由非零数字组成的数 $N$，找出由 $N$ 的各位数字重新排列能得到的最小的数 $M$。 解决这个问题十分容易。

至此，我们成功解决了这道问题。