神奇的自然数

显示全部楼层 · 2010-9-1 19:55:17

神奇的自然数
源程序名
number.pas
输入文件名：number.in
输出文件名：number.out
我们知道自然数有无穷多个，而每个自然数也有无穷多个倍数，现在的问题很简单：对于一个给定的自然数n，找出它的倍数中包含数字最少的那个数，如果存在多个，请求出最小的一个。
输入:
输入一行，为一个数n。
输出:
输出一行，为一个数s，表示包含数字最少且最小的n的倍数。
样例:
number.in
13
number.out
111111
数据范围
30%的数据n<=500
60%的数据n<=5000
100%的数据n<=20000
下面是提示，但是不知道怎么做：
经过尝试发现可以用1个或者2个数字就可以达到目标了。
首先尝试1个数字，只要枚举1~9之间的一个数i，利用对n的余数为0来判断是否满足要求。N位数字的余数可以用N-1位得到的来求：new=(old*10+i) mod n，同时如果当前得到余数已经出现过，就说明只用数字i是不可能得到n的倍数的，所以可以退出枚举下一个i。
如果1位数字不行，那就尝试2个数字。2个数字还是采用余数的想法，枚举了两个数字x、y之后，设f[i,j]表示用x、y组成的i位数字mod n为j是否可行，值得注意的是要求出最小的数字，所以我们每次要枚举最高位，并且要进行一个二选一。
整个算法的时间复杂度为o(9*n+10*9/2*n*L)=o(45*L*n)，这里的L是2个数字时答案的长度，事实证明这个L<=30。
PS:不会别瞎搞

千问 · 2010-9-1 19:55:17

n它本身就是n1倍后的数，只要乘后不加数位，就是包含数字数位最少的数，试试乘小数O(∩_∩)O~

千问 · 2010-9-1 19:55:17

1+1