1967. 灵梦の蜜汁富婆值

刚考完试的⑨转头出门就被灵梦拎了起来,问了一个送命题

如果琪露诺答不出来的话,就要被绝凶の灵梦使用「完全退治」

为了保命,⑨不得不计算灵梦の富婆值

对于整数 aa,规定其从左到右的各个数位分别为 a1,a2,,ana_1,a_2,\cdots,a_n,即: a=a1a2an a=\overline{a_1a_2\cdots a_n}

定义整数 aa 的富婆值 p(a)p(a) 是它的每一位除以从它开始往左的位数加一的余数的乘积:

p(a)=i=1n(aimod(i+1)) =(a1mod2)×(a2mod3)××(an1modn)×(anmod(n+1)) \begin{aligned} p(a)&=\prod_{i=1}^n(a_i \bmod (i+1)) \ &= (a_1\bmod 2) \times (a_2 \bmod 3) \times \cdots \times (a_{n-1} \bmod n) \times (a_n \bmod (n+1)) \end{aligned}

其中 mod\bmod 为取余运算,即求两个数相除的余数,如 7mod3=17\bmod3=1

对于 a=5719a=5719,它的富婆值 p(a)p(a) 是:

p(a)=(5mod2)×(7mod3)×(1mod4)×(9mod5)=1×1×1×4=4 \begin{aligned} p(a)&=(5\bmod 2)\times (7\bmod 3) \times (1\bmod 4) \times (9\bmod 5) \\ &=1\times 1\times 1\times 4=4 \end{aligned}

给定整数 aa,试找到一个只包含阿拉伯数字且长度不超过 10001000 的字符串 ss,使得存在一种插入方案,在 aa 的其中两个相邻数位之间插入 ss 后,新得到的整数 aa' 的富婆值 p(a)p(a') 小于原有整数 aa 的富婆值 p(a)p(a)

例如对于 a=5719a=5719,考虑字符串 11,仅考虑插入的位置共 33 种方案,得到的数 aa' 分别是:

511719,571119,571119 511719,571119,571119

这三个数的富婆值分别是 4,2,24,2,2,可以发现 11 是符合题意的。

输入

输入只有一行,包含一个整数 a (12a9899999)a \ (12 \leq a \leq 9899999)

保证给定的输入满足 p(a)2p(a) \geq 2

输出

在一行内输出字符串 ss。如果有多个符合条件,你只需要输出任意一个。

可以证明在给定条件下一定存在满足条件的字符串 ss

样例

标准输入 复制文本
5719
标准输出 复制文本
11
标准输入 复制文本
957
标准输出 复制文本
2
标准输入 复制文本
78787
标准输出 复制文本
6

提示

对于样例 11a=5719a=5719,富婆值是 44,可以插入 1111 变成 571119571119,富婆值为 22

对于样例 22a=957a=957,富婆值是 66,可以插入 22 变成 92579257,富婆值为 44

对于样例 33a=78787a=78787,富婆值是 1818,可以插入 66 变成 768787768787,富婆值为 44

来源

2023 SCNUCPC 网络赛 (重现)

登录以提交代码。
单点时限 1 秒
内存限制 256 MB
提交 20
通过 14