问题 4530 --G

4530: G

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

有一天,奔奔在上数学辅修课,讲台上数分老师的课讲得实在过于无聊,奔奔终于按捺不住开起了小差。奔奔在稿纸上乱写乱画,突然发现了一个好玩的游戏。

假设有任意一个正整数a0,奔奔希望找到一个X序列  ,使得ai+1 总是 ai的一个子序列,并且从 ai ai+1的过程中剔除掉的数位所直接构成的数(这样的剔除构成的数必须为一个合法正整数),总是能够整除ai 

合法正整数定义如下:

大于1

无前导0

始终为a0的子序列

这里给出一个具体例子:

2004   4

2004   200   0

第一行中2004将数位22004中剔除,得到子序列004,剔除前导0转化为自然数4,并且剔除的数位2整除了2004

同理第二行中的2004剔除了数位4,得到子序列200200进一步剔除了2

奔奔对一个特定的正整数,总是希望能够找到一个长度尽可能长的X序列。当然,同样长度的X序列可能有两个,那么我们对两个X序列从第一项到最后一项逐个比较,第一次出现差异的时候,自然数值较小的项所在的序列将被我们选择。同理,若有多个X序列长度相同,按同样的规则取最小项所在序列。

详细的情形参考下文用例。

输入

输入包含多个正整数,每一个正整数小于十亿,不含前导0,该数字独占一行。输入的结束以0为标志,0不做处理。

输出

对于每一个正整数用例,输出所求最大可能长度的X序列,该序列独占一行,两两之间以一个空格分隔。

样例输入

123456789
7
2004
6341
8013824
0

样例输出

123456789 12345678 1245678 124568 12456 1245 124 12 1
7
2004 200 0
6341
8013824 13824 1324 132 12 1

来源

[提交][状态]