想起来的之前做模拟赛遇到过的几乎一模一样的题目:
小Z是个特别堕落的小朋友，上数学课的时候经常有奇奇怪怪的想法。
一天，小Y调动了所有的军队，向小Z所在的总部攻来，战火已到了小Z的课桌外。但勇士们都是临危不乱。小Z虽然没有直接在战场上冲锋，但他却坐在控制中心的电脑旁，运筹帷幄，决胜千里。从战场中会不断有数字发来，表示自己或者敌人军队人的数目。但是，为了保密，这个数字不是直接发来的，而是把它平方后，取它的最后9位数（不足就补0）。小Z收到了这个数后，需要知道这个原来的数字，这个数字会小于109。小Z需要从小到大输出所有可能的数。但由于小Z的数学……，所以他来找你帮忙。
保证答案的个数不超过4000个。
输入一行，一个长度为9的数，前面可以是0。
从小到大输出所有可能的数，每个数一行，如果那个数不足9位，就在前面输出0。
by 2016gdgzoi471 @ 2018-04-26 20:39:34
逐位搜索，（从小到大看位数）搜到第k位时，保证前k位的平方取前k位和目标的前k位相同即可。~~(某位haiq的题解)~~
by 2016gdgzoi471 @ 2018-04-26 20:42:04