洛谷U148838 数学黑洞 题解
题目链接：U148838 数学黑洞
本题为私题，作者 q779 （没错，就是本人！）
题意：
给定 \(N \le 10^{114514}\) ，求 \(F(N)=f(f(f(\cdots f(N))))\) 。
其中 \(f(N)=N\) 中偶数的个数 \(\times 100+ N\) 中奇数的个数 \(\times 10 + N\) 的位数。
例如 \[ f(345)=1\times100+2\times10+3=123 \] 题目保证一定有解。
输入：一行，\(N\) 。 输出：一行，答案。
这道题是我初中的时候出的，当时从学校的数学报纸上看到的，难度评级入门到普及-吧。
实际上就是“西西弗斯串”（也叫 \(123\) 数字黑洞），有兴趣可以百度（百度写的还可以）。
注意到 \(f(123)=123\) ，即 \(123\) 是原题的一个不动点。有趣的是，实际上任何 \(N \in \mathbb{Z}\) 有 \(F(N)=123\) 。
以下记 \(f\) 中的三个数分别为 \(a,b,c\) ，即 \(f(N) = 100a + 10b + c\) 。
证明其实很简单，我们只需要分类讨论即可
- 当 \(N\) 是一位数时
- 若 \(N\) 为奇数，则 \(a=0,~b=1,~c=1\) 得到 \(011\) ，接着 \(a=1,~b=2,~c=3\) 得到 \(123\) 。
- 若 \(N\) 为偶数，则 \(a=1,~b=0,~c=1\) 得到 \(101\) ，接着 \(a=1,~b=2,~c=3\) 得到 \(123\) 。
- 当 \(N\) 是两位数时
- 一奇一偶，则 \(a=1,~b=1,~c=2\) 得到 \(112\) ，接着 \(a=1,~b=2,~c=3\) 得到 \(123\) 。
- 两个奇数，则 \(a=0,~b=2,~c=2\) 得到 \(022\) ，然后得到 \(303\) ，最后还是得到 \(123\) 。
- 两个偶数，则 \(a=2,~b=0,~c=2\) 得到 \(202\) ，然后得到 \(303\) ，最后还是得到 \(123\) 。
- 当 \(N\) 是三位数时
- 三个偶数，则 \(a=3,~b=0,~c=3\) 得到 \(303\) ，接着 \(a=1,~b=2,~c=3\) 得到 \(123\)
- 三个奇数，则 \(a=0,~b=3,~c=3\) 得到 \(033\) ，接着 \(a=1,~b=2,~c=3\) 得到 \(123\)
- 两个偶数+一个奇数，则 \(a=2,~b=1,~c=3\) 得到，接着 \(a=1,~b=2,~c=3\) 得到 \(123\)
- 一个偶数+两个奇数，则 \(a=1,~b=2,~c=3\) 直接得到 \(123\) 。
- 当 \(N\) 是四位数即四位数以上时，\(c=a+b\) ，显然一次变化后比 \(N\) 小，最终一定变成三位数的情况。\(\square\)
所以只需要输出 \(123\)
即可。时间复杂度 \(\mathcal{O}(1)\)
，主要代码就是：puts("123") 。
参考文献：
你别说，我出这题的时候还真不会证明呢（那时候哪有空证明这种东西啊）。
