给定一个自然数N，寻找一个M，使得M是N的倍数，M是由0和1组成的十进制数

可能这个题大家见过很多次了，但我还是不会做
我尝试一位一位地求M/N的值，但是因为我程序不完善导致出现了无限长而且循环的M/N
而且按照我的想法即使能求出M，M也可能不是最小的
请大家告诉我一下思路~谢谢

162 个解决方案

#1

我想的比较笨的办法就是，
依次取N的从小到大的正整数倍；
对每个倍数M'，通过mod10来判断是否由0，1构成；
最先得到的倍数，就是最小的M

#2

是要找到最小的么？m和n的范围有没有限制？如果不是找最小的，应该有O(n)的方法（也许还有更好的，没有太仔细想），如果是找最小的，
可能会稍微复杂一些，不知道有没有什么好的构造的方法！

#3

引用 2 楼 litaoye 的回复:

是要找到最小的么？m和n的范围有没有限制？如果不是找最小的，应该有O(n)的方法（也许还有更好的，没有太仔细想），如果是找最小的， 
可能会稍微复杂一些，不知道有没有什么好的构造的方法！

到底是什么方法~
呵呵

#4

引用 3 楼 LeonTown 的回复:

引用 2 楼 litaoye 的回复:
是要找到最小的么？m和n的范围有没有限制？如果不是找最小的，应该有O(n)的方法（也许还有更好的，没有太仔细想），如果是找最小的， 
可能会稍微复杂一些，不知道有没有什么好的构造的方法！ 



到底是什么方法~ 
呵呵

(?*10)%N这个序列肯定会有N步内结束或有循环，那么在这个循环节上取N个1，其它位取0就一定是N的倍数。

#5

求最小序列可以转换为N次类似背包问题

#6

给出了一个实现，供参考。

package org.tibetjungle.demo;

public class NatrualNumberFinder {

	private int referenceNumber = 0;

	public NatrualNumberFinder( int referenceNumber ) {

		this.referenceNumber = referenceNumber;
	}
	public void setReferenceNumber( int referenceNumber ){

		this.referenceNumber = referenceNumber;
	}

	/**根据位数要求，生成一个为只有0、1的10进制数。
	 * 这里用到了将一个数转换为二进制数的算法
	 * @param numberOfDigital 生成的十进制数的位数
	 * @param sequence 序号，这个书号是从0 到 （ 2 ** numberOfDigital - 1 ）
	 */
	private static long generateDigital( int numberOfDigital, int sequence ) {

		StringBuffer serial = new StringBuffer( "" );
		char currentNumber[] = null;

		//将sequence进制数转换为二进制数（反序）
		while ( sequence >= 1 ) {

			serial.append( sequence % 2 );
			sequence = ( int ) Math.floor( sequence / 2 );
		}

		int length = serial.toString().length();

		//填充
		for ( int i = 1; i < numberOfDigital - length; i ++ )
			serial.append( "0" );

		//最高位总是为1	
		serial.append( "1" );

		if ( null == currentNumber )
			currentNumber = new char[ numberOfDigital ];

		for ( int i = 0; i < serial.toString().length(); i ++ ) {

			currentNumber[ i ] = serial.toString().charAt(
					numberOfDigital - i - 1 );
		}

		String digital = "";
		//恢复顺序
		for ( int i = 0; i < numberOfDigital; i ++ )
			digital = currentNumber[ numberOfDigital - i - 1 ] + digital;
		//生成十进制数
		return Long.parseLong( digital );

	}

	public long find() {

		if ( 0 == referenceNumber || 1 == referenceNumber )
			return referenceNumber;
		return doFind( 2 );
	}

	public long doFind( int numberOfDigital ) {

		int loops = ( int ) Math.pow( 2, numberOfDigital - 1 );

		for ( int i = 0; i < loops; i ++ ) {

			long testedNumber = NatrualNumberFinder.generateDigital(
					numberOfDigital, i );
			if ( testedNumber % referenceNumber == 0 )
				return testedNumber;

		}

		return doFind( numberOfDigital + 1 );
	}

	/**
	 * @param args
	 */
	public static void main( String[] args ) {

		NatrualNumberFinder natrualNumberFinder = new NatrualNumberFinder( 34 );
		for( int i = 1;  i <= 88; i ++ ){

			natrualNumberFinder.setReferenceNumber( i );
			System.out.println( "reference = " + i + ", tested = " + natrualNumberFinder.find() );
		}

	}

}

#7

把结果贴出来：
reference = 1, tested = 1
reference = 2, tested = 10
reference = 3, tested = 111
reference = 4, tested = 100
reference = 5, tested = 10
reference = 6, tested = 1110
reference = 7, tested = 1001
reference = 8, tested = 1000
reference = 9, tested = 111111111
reference = 10, tested = 10
reference = 11, tested = 11
reference = 12, tested = 11100
reference = 13, tested = 1001
reference = 14, tested = 10010
reference = 15, tested = 1110
reference = 16, tested = 10000
reference = 17, tested = 11101
reference = 18, tested = 1111111110
reference = 19, tested = 11001
reference = 20, tested = 100
reference = 21, tested = 10101
reference = 22, tested = 110
reference = 23, tested = 110101
reference = 24, tested = 111000
reference = 25, tested = 100
reference = 26, tested = 10010
reference = 27, tested = 1101111111
reference = 28, tested = 100100
reference = 29, tested = 1101101
reference = 30, tested = 1110
reference = 31, tested = 111011
reference = 32, tested = 100000
reference = 33, tested = 111111
reference = 34, tested = 111010
reference = 35, tested = 10010
reference = 36, tested = 11111111100
reference = 37, tested = 111
reference = 38, tested = 110010
reference = 39, tested = 10101
reference = 40, tested = 1000
reference = 41, tested = 11111
reference = 42, tested = 101010
reference = 43, tested = 1101101
reference = 44, tested = 1100
reference = 45, tested = 1111111110
reference = 46, tested = 1101010
reference = 47, tested = 10011
reference = 48, tested = 1110000
reference = 49, tested = 1100001
reference = 50, tested = 100
reference = 51, tested = 100011
reference = 52, tested = 100100
reference = 53, tested = 100011
reference = 54, tested = 11011111110
reference = 55, tested = 110
reference = 56, tested = 1001000
reference = 57, tested = 11001
reference = 58, tested = 11011010
reference = 59, tested = 11011111
reference = 60, tested = 11100
reference = 61, tested = 100101
reference = 62, tested = 1110110
reference = 63, tested = 1111011111
reference = 64, tested = 1000000
reference = 65, tested = 10010
reference = 66, tested = 1111110
reference = 67, tested = 1101011
reference = 68, tested = 1110100
reference = 69, tested = 10000101
reference = 70, tested = 10010
reference = 71, tested = 10011
reference = 72, tested = 111111111000
reference = 73, tested = 10001
reference = 74, tested = 1110
reference = 75, tested = 11100
reference = 76, tested = 1100100
reference = 77, tested = 1001
reference = 78, tested = 101010
reference = 79, tested = 10010011
reference = 80, tested = 10000
reference = 81, tested = 1111111101
reference = 82, tested = 111110
reference = 83, tested = 101011
reference = 84, tested = 1010100
reference = 85, tested = 111010
reference = 86, tested = 11011010
reference = 87, tested = 11010111
reference = 88, tested = 11000

#8

就是5楼说的方法，比如n = 7,在1,11,111,1111,11111,111111,1111111,11111111 这8个数中一定存在2个数mod 7相等的（抽屉原则)

假设为A和B，那么A - B = M M一定是7的倍数，且M一定可以写为1和0组成的数！

引用 3 楼 LeonTown 的回复:

引用 2 楼 litaoye 的回复:

是要找到最小的么？m和n的范围有没有限制？如果不是找最小的，应该有O(n)的方法（也许还有更好的，没有太仔细想），如果是找最小的， 
可能会稍微复杂一些，不知道有没有什么好的构造的方法！ 


到底是什么方法~ 
呵呵

#9

大数取余?

#10

宽搜如果余数已经出现则该条道路去掉

#11

想了很久，没有想到捷径。

#12

关注中

#13

想到了一个效率高一些的方法，先对n进行因数分解，比如30 = 2*5*3,然后分别按照上面的方法，找到其因子对应的F(n)
10,10,111然后就可以构造出一个数m，m前面有3个1(1*1*3)，后面有2个0(所有0的个数的和) => 11100

#14

类似于八楼的做法，例如n=7 取{1，10，100，1000，10000，100000} 他们对7的余数{1，3，2，6，4，5}，只要从这个集合里面找出前几个数字相加可以等于7就可以了，那几个余数对应的原来的数相加，就是符合要求的最小的数。比如说7是1+6对应原来的数字1+1000=1001。用这种方法应该可以。

#15

关注

#16

我来个最笨的。1楼的方法

import java.util.*;
public class Number {
	public static void main(String []s) {
		String arg = null;
		Scanner scan = new Scanner(System.in);
		while( !(arg = scan.next()).equals("exit") ) {
			int i = 1;
			Integer n = new Integer(arg);
			while(true) {
				Integer m = n*i;
				if (m.toString().matches("[01]*") ) {
					System.out.println(n+" : "+ m);
					break;
				}
				i++;
			}
		}
	}
}

1
1 : 1
2
2 : 10
3
3 : 111
4
4 : 100
5
5 : 10
6
6 : 1110
7
7 : 1001
8
8 : 1000
9
9 : 111111111
10
10 : 10
11
11 : 11
12
12 : 11100
13
13 : 1001
14
14 : 10010
15
15 : 1110
16
16 : 10000
324
324 : 10111100

#17

总体思想：从低位逐位向上归0、1

N为奇数
那第a-1位数为0、1跳过(就基数是10的a次方)，其他用N的10^a倍补充成0

如下：
如个位为1就跳过；十位为7，就加上  10*（10-7） * N；百位为x，就加上  100*（10-x） * N，一直向上累加。


N为偶数
那位数y为0、1跳过，y为奇数就加上  10^a*（11-y） * N;y为奇数就加上  10^a*（10-y） * N,一直向上累加。

N为10的倍数，先去掉尾部的零，等按前述步骤得到结果后再补回尾部的零。

#18

列个补充的表
个位数            对应某位数 （0、1跳过）          
                  2|3|4|5|6|7|8|9
0 去掉
1 应当加上的N倍数 2|3|4|5|6|7|8|9
2 应当加上的N倍数 4|4|3|3|2|2|1|1
3 应当加上的N倍数 3|6|2|2|5|1|1|4
……

#19

厉害的人多啊

#20

niu a!

#21

你不规定一定的范围，那就是死循环了。楼主再看看~~~~~··

#22

oooooooooooooooo

#23

这个方法貌似不错。。。
执行效率上要好一些
但是如果给出的整数比较大的话可能会溢出。。。

#24

引用 17 楼 zeroieme 的回复:

总体思想：从低位逐位向上归0、1

N为奇数
那第a-1位数为0、1跳过(就基数是10的a次方)，其他用N的10^a倍补充成0

如下：
如个位为1就跳过；十位为7，就加上10*（10-7） * N；百位为x，就加上100*（10-x） * N，一直向上累加。


N为偶数
那位数y为0、1跳过，y为奇数就加上10^a*（11-y） * N;y为奇数就加上10^a*（10-y） * N,一直向上累加。

N为10的倍数，先去掉尾部的零，等按前述步骤得到结果后再补回尾部的零。

 肯定能够保证被N整除，但是无法满足0，1的条件！！

#25

i初始值为1步长为1递增的自然数，让N乘以i结果为M,循环直到M值为0和1组成的十进制数为止（加判断）
不知可否

#26

public static int GetNumber (int _i)
{
   int x = 0;
   int y = 0;
   for(;;)
   {
     x++;
     y = _i * x;
     if (new Regex("^[0-1]+$").Match(s.ToString).Success)
     {
         return s;           
     }
   }
}

发上来大家看看

#27

 关注中。。。

#28

public static int GetNumber (int _i)
{
   int x = 0;
   int y = 0;
   for(;;)
   {
     x++;
     y = _i * x;
     if (new Regex("^[0-1]+$").Match(y.ToString).Success)
     {
         return y;           
     }
   }
}

#29

t=1
while(t)
{

m=10^0*(0-1)+10^1*(0-1)+..+10^(t-1)*(0-1)
 if(m!=0&&m%n==0)
  break;
 t++;
}

先把问题读明白了
又是大数处理问题 
数学大师在那里
[img=http://3333.800y.net/showpic.asp][/img]

#30

高手如云呀！

#31

#include <stdio.h>
#define MAX_SIZE 1111111112
int fun(int x){
	int i,a,b;
	i=1;
	while(1){
		a=x*i;b=a;i++;
		if(b>MAX_SIZE) return -1;
		while((a%10)==1||(a%10)==0){
			if(a==0||a==1) return b;
			else a/=10;
		}
	}
	return b;
}

int main(){
	int i,b;
	for(i=0;i<89;i++){
		b=fun(i);
		if(b==-1) printf("%d not find in MAX_SIZE!\n",i);
		else printf("%d=>%d\n",i,b);
	}
	return 0;
}

0=>0
1=>1
2=>10
3=>111
4=>100
5=>10
6=>1110
7=>1001
8=>1000
9=>111111111
10=>10
11=>11
12=>11100
13=>1001
14=>10010
15=>1110
16=>10000
17=>11101
18=>1111111110
19=>11001
20=>100
21=>10101
22=>110
23=>110101
24=>111000
25=>100
26=>10010
27=>1101111111
28=>100100
29=>1101101
30=>1110
31=>111011
32=>100000
33=>111111
34=>111010
35=>10010
36 not find in MAX_SIZE!
37=>111
38=>110010
39=>10101
40=>1000
41=>11111
42=>101010
43=>1101101
44=>1100
45=>1111111110
46=>1101010
47=>10011
48=>1110000
49=>1100001
50=>100
51=>100011
52=>100100
53=>100011
54 not find in MAX_SIZE!
55=>110
56=>1001000
57=>11001
58=>11011010
59=>11011111
60=>11100
61=>100101
62=>1110110
63=>1111011111
64=>1000000
65=>10010
66=>1111110
67=>1101011
68=>1110100
69=>10000101
70=>10010
71=>10011
72 not find in MAX_SIZE!
73=>10001
74=>1110
75=>11100
76=>1100100
77=>1001
78=>101010
79=>10010011
80=>10000
81=>1111111101
82=>111110
83=>101011
84=>1010100
85=>111010
86=>11011010
87=>11010111
88=>11000
Press any key to continue

【说明】
设置MAX_SIZE为1111111112的原因是int的取值范围在-2147483648~2147483647之间
2147483647
1111111112

#32

看看就行了

#33

用加法代替乘法：

#include <stdio.h>
#define MAX_SIZE 1111111111
void fun(int x){
	int a,b;
	a=x;b=a;
    while(1){
        if(b>MAX_SIZE){
			printf("%d not find in MAX_SIZE!\n",x);return;
		}
        while((a%10)==1||(a%10)==0){
            if(a==0||a==1){
				printf("%d=>%d\n",x,b);return;
			}
            else a/=10;
        }
		a=x+b;b=a;
    }
}

int main(){
    int i;
    for(i=0;i<89;i++) fun(i);
    return 0;
}

#34

楼上的算法有一个错误，显然的，0不是0的倍数

#35

其实在unsigned int范围内，全由1、0组成的数（0除外）一共就1023个，何不全部找出来，然后查表，这样的效率是最高的！

#36

我不说话。

#37

写了个非常高效的，而且可以计算大数的算法，先把结果贴出来，大家看一下对不

89 ==> 11010101
90 ==> 1111111110
91 ==> 1001
92 ==> 11010100
93 ==> 10000011
94 ==> 100110
95 ==> 110010
96 ==> 11100000
97 ==> 11100001
98 ==> 11000010
99 ==> 111111111111111111
100 ==> 1000
101 ==> 1010
102 ==> 1000110
103 ==> 11100001
104 ==> 1001000
105 ==> 101010
106 ==> 1000110
107 ==> 100010011
108 ==> 110111111100
109 ==> 1001010111
110 ==> 1100
111 ==> 1110
112 ==> 10010000
113 ==> 1011011
114 ==> 110010
115 ==> 1101010
116 ==> 110110100
117 ==> 10101111111
118 ==> 110111110
119 ==> 100111011
120 ==> 111000
121 ==> 11011
122 ==> 1001010
123 ==> 10001100111
124 ==> 11101100
125 ==> 1000
126 ==> 11110111110
127 ==> 11010011
128 ==> 10000000
129 ==> 100100001
130 ==> 10010
131 ==> 101001
132 ==> 11111100
133 ==> 11101111
134 ==> 11010110
135 ==> 11011111110
136 ==> 11101000
137 ==> 10001
138 ==> 100001010
139 ==> 110110101
140 ==> 100100
141 ==> 10011
142 ==> 100110
143 ==> 1001
144 ==> 1111111110000
145 ==> 11011010
146 ==> 100010
147 ==> 1100001
148 ==> 11100
149 ==> 110111
150 ==> 11100
151 ==> 1110001
152 ==> 11001000
153 ==> 10111110111
154 ==> 10010
155 ==> 1110110
156 ==> 1010100
157 ==> 10101101011
158 ==> 100100110
159 ==> 100011
160 ==> 100000
161 ==> 11101111
162 ==> 11111111010
163 ==> 1010111
164 ==> 1111100
165 ==> 1111110
166 ==> 1010110
167 ==> 11111011
168 ==> 10101000
169 ==> 10111101
170 ==> 111010
171 ==> 1111011111
172 ==> 110110100
173 ==> 1011001101
174 ==> 110101110
175 ==> 100100
176 ==> 110000
177 ==> 100101111
178 ==> 110101010
179 ==> 11010111
180 ==> 11111111100
181 ==> 1001111
182 ==> 10010
183 ==> 100101
184 ==> 110101000
185 ==> 1110
186 ==> 100000110
187 ==> 1001011
188 ==> 1001100
189 ==> 1010111010111
190 ==> 110010
191 ==> 11101111
192 ==> 111000000
193 ==> 11001
194 ==> 111000010
195 ==> 101010
196 ==> 110000100
197 ==> 1101000101
198 ==> 1111111111111111110
199 ==> 111000011


我在笔记本上运行出上面的结果不超过5秒。请注意99和198的结果！

#38

10000 ==> 100000
10001 ==> 100010
10002 ==> 1000000010010
10003 ==> 1111111000000001
10004 ==> 111000010001100
10005 ==> 100010000010
10006 ==> 111011000010010
10007 ==> 1000101011001
10008 ==> 100111101111000
10009 ==> 10111000100001001111
10010 ==> 100100
10011 ==> 100110
10012 ==> 1011100000011100
10013 ==> 110001001111111
10014 ==> 1100010011010
10015 ==> 1000011110010
10016 ==> 1100101100000
10017 ==> 11000010111111
10018 ==> 1011011000010
10019 ==> 1110111001001
10020 ==> 10000010100
10021 ==> 10001001000111
10022 ==> 1101010110101110
10023 ==> 10101110111001
10024 ==> 11010111000
10025 ==> 111101100100
10026 ==> 101111111000010
10027 ==> 111111111111111
10028 ==> 1110010100100
10029 ==> 111011001
10030 ==> 1111100000010
10031 ==> 10000001010111
10032 ==> 1111000110000
10033 ==> 110000000010101
10034 ==> 1100010011010
10035 ==> 101110111110
10036 ==> 101110010101100
10037 ==> 11000110101001
10038 ==> 1110000101110110
10039 ==> 111101101011
10040 ==> 110001001000
10041 ==> 1010100110001
10042 ==> 110010110
10043 ==> 1101000100101
10044 ==> 110011101110100
10045 ==> 1001000101010
10046 ==> 101001010101110
10047 ==> 1101110001101001
10048 ==> 10101101011000000
10049 ==> 100110111111101
10050 ==> 1001000100
10051 ==> 1011111111111
10052 ==> 10100010111100
10053 ==> 11010110110101
10054 ==> 1110010010010
10055 ==> 100100101111110
10056 ==> 111110001000
10057 ==> 1111011101111
10058 ==> 110111110111010
10059 ==> 1010100011010111
10060 ==> 110100010100
10061 ==> 111100011101
10062 ==> 10111101101010
10063 ==> 100001101011101
10064 ==> 1000110000
10065 ==> 11011110
10066 ==> 1000010011101010
10067 ==> 11100110100011
10068 ==> 11110001000100
10069 ==> 111010010101
10070 ==> 111111101110
10071 ==> 1001100111111
10072 ==> 100001111000
10073 ==> 10001101011111
10074 ==> 1000110101010
10075 ==> 11100111100
10076 ==> 1000010001100
10077 ==> 11010100100001
10078 ==> 10000110111010
10079 ==> 100011100111001
10080 ==> 111101111100000
10081 ==> 1000110011101
10082 ==> 1110011111010
10083 ==> 100010110101111
10084 ==> 100111101001100
10085 ==> 100110111010010
10086 ==> 10110101101000110
10087 ==> 10111101101101
10088 ==> 1110110001000
10089 ==> 10011011011011
10090 ==> 100100011111110
10091 ==> 111001
10092 ==> 11000100110100
10093 ==> 100001010001
10094 ==> 100010101000110
10095 ==> 1001000010
10096 ==> 1010111110000
10097 ==> 111111101000101
10098 ==> 111111111111101101110
10099 ==> 100110001001010111
10100 ==> 101000
10101 ==> 101010
10102 ==> 100000100110110
10103 ==> 110011110011001
10104 ==> 101010101001000
10105 ==> 1000011010
10106 ==> 111000110010
10107 ==> 11101101001011
10108 ==> 1110111100
10109 ==> 1001001000110111
10110 ==> 101100
10111 ==> 101110
10112 ==> 100100110000000
10113 ==> 110001001000101
10114 ==> 1010110111010
10115 ==> 100000001111010
10116 ==> 11101111001100
10117 ==> 100001011001
10118 ==> 1000100000110
10119 ==> 1101111001100001
10120 ==> 11111001000
10121 ==> 100001101011101
10122 ==> 10011111010110
10123 ==> 101100001011011
10124 ==> 10110100001100
10125 ==> 1111111101000
10126 ==> 1101000000100110
10127 ==> 11111000011111
10128 ==> 1100010100110000
10129 ==> 100100001110011
10130 ==> 100001101010
10131 ==> 110111000000001
10132 ==> 1001000101101100
10133 ==> 1001110001
10134 ==> 111010101101010
10135 ==> 100010011110
10136 ==> 101011110011000
10137 ==> 1110111010011
10138 ==> 11101110
10139 ==> 10010010111011
10140 ==> 1011110100
10141 ==> 1100010100101
10142 ==> 11110101111010
10143 ==> 1111001100111
10144 ==> 100000011111100000
10145 ==> 1001110000010
10146 ==> 100000001101110
10147 ==> 10110000111111
10148 ==> 11100010011100
10149 ==> 1001011101000111
10150 ==> 1101011100
10151 ==> 10110000111
10152 ==> 111101101011000
10153 ==> 11011101101
10154 ==> 10111100010010
10155 ==> 100110000101010
10156 ==> 110010010100100
10157 ==> 1110010010011
10158 ==> 11010010001011110
10159 ==> 110000100101001
10160 ==> 110100110000
10161 ==> 1001111011011
10162 ==> 111001101110
10163 ==> 100111101000111
10164 ==> 111111011111100
10165 ==> 1000000111010
10166 ==> 100011011110010
10167 ==> 110010110101101
10168 ==> 1001001001001000
10169 ==> 10111110110011
10170 ==> 1100111101110
10171 ==> 1000011001101
10172 ==> 1000011100100
10173 ==> 1010110100001
10174 ==> 1010001111110
10175 ==> 11111100
10176 ==> 100011000000
10177 ==> 10101110111
10178 ==> 1101000010110
10179 ==> 11100001101111
10180 ==> 10010110001100
10181 ==> 10001010101
10182 ==> 101000100101010
10183 ==> 1110110101111
10184 ==> 101111000001000
10185 ==> 11101100010
10186 ==> 1011111100010
10187 ==> 100011111110101
10188 ==> 110111110100100
10189 ==> 10111101111101
10190 ==> 11011100010
10191 ==> 1010111100001011
10192 ==> 101111010000
10193 ==> 10000111001111
10194 ==> 11101101010110
10195 ==> 110010111111010
10196 ==> 111011101101100
10197 ==> 11101101111111111111
10198 ==> 110111110101010
10199 ==> 1000010111110101

应该是对的，有效代码已经优化到30行了，正在添加注释

#39

放出代码，请各位欣赏，绝对大师级水准，呵呵！

不给我分可说不过去了，这应该是本贴中最优秀的实现了吧？

有点狂了，别介意！

#include <math.h>
#include <string>
#include <iostream>
#include <vector>

// 以下函数尝试找出一个全部由1、0组成，并能被n整除的自然数。结果存入strOut。
// 算法过程是生成比n大的所有全部由1、0组成的数，并逐个判断。
// 此算法仍有很大优化的余地，比如用bitset代替vector，排除素数解，跳过整数倍等等。
// 考虑到代码长度及可读性，以及本题的意义和规模，再进行优化是没有必要的。
// 经测试，全局优化编译的版本，在2.1GHz的CPU上运行结果如下：
// 1至998：12.9879s（注：999的解超过30位，未能得出结果）
int Test( unsigned int n, std::string &strOut )
{
	// 定义存放大数数组的容器及迭代器
	std::vector<unsigned char> vecMul;
	std::vector<unsigned char>::iterator iCurBit;
	std::vector<unsigned char>::reverse_iterator riCurBit;
	// nStartBit为给定整数的位数+1，即最小可能解的位数
	unsigned int nDividend, nStartBit =
		(unsigned int)floor( log10( (float)n ) + 1.0f ) + 1;
	// vecMul以数组形式存放解，头部为低位，尾部为高位，赋初值为100...
	vecMul.resize( nStartBit, 0 );
	*vecMul.rbegin() = 1;
	// 大循环逐个生成可能的解，并判断是否能被给定数整除。解超过xx位视为无解
	for ( nDividend = 1; nDividend != 0 && vecMul.size() < 28; *iCurBit = 1 )
	{	// 下面的循环用于计算数组除法，原理与手算法类似
		for( nDividend = 0, riCurBit = vecMul.rbegin();
			riCurBit < vecMul.rend(); nDividend %= n )
			// nDividend为被除数和余数
			for ( unsigned int nDividendBit = (unsigned int)floor( log10(
				(float)nDividend ) + 1.0f ); nDividendBit < nStartBit &&
				riCurBit < vecMul.rend(); ++nDividendBit, ++riCurBit )
				// 在这一步中，上一次除得的余数和所给数接下来的位再组成被除数
				nDividend = nDividend * 10 + *riCurBit;
		// 当余数为0即表示已得出答案
		if ( nDividend == 0 )
			// 将数组中每一个数变为字符，输出到参数字串对象中
			for ( strOut.clear(), riCurBit = vecMul.rbegin();
				riCurBit < vecMul.rend(); ++riCurBit )
				strOut.push_back( *riCurBit + '0' );
		// 生成下一个全由1、0组成的数，原理和2进制数进位法相同
		for ( iCurBit = vecMul.begin(); iCurBit != vecMul.end() &&
		// 从低向高找到第一个0，将其左边的数全部置0，然后将其至1即完成进位
			*iCurBit == 1; *(iCurBit++) = 0 );
		// 如果一直到最高位都为1，则为数组增加一位。
		if ( iCurBit == vecMul.end() )
			iCurBit = vecMul.insert( vecMul.end(), 1 );
	}
	return nDividend;
}

// 以下为主函数及测试代码，结构简单，不再描述
void main( int argc, char* argv[] )
{
	std::string strResult;
	for ( int i = 1; i < 999; ++i )
		if ( 0 == Test( i, strResult ) )
			std::cout << i << " ==> " << strResult << std::endl;
}

#40

引用 38 楼 fireseed 的回复:

10000 ==> 100000 
10001 ==> 100010 
10002 ==> 1000000010010 
10003 ==> 1111111000000001 
10004 ==> 111000010001100 
10005 ==> 100010000010 
10006 ==> 111011000010010 
10007 ==> 1000101011001 
10008 ==> 100111101111000 
10009 ==> 10111000100001001111 
10010 ==> 100100 
10011 ==> 100110 
10012 ==> 1011100000011100 
10013 ==> 110001001111111 
10014 ==> 1100010011010 
10015 ==> 100001…

10000 ==> 100000 
其实10000本身就满足条件了，1倍也是倍数啊。

#41

实际上这个程序更简单：
#include <iostream>
using namespace std;
main(){
for(unsigned int i=0;i<99999;i++) cout<<"i="<<i<<"==>0"<<endl;
}

0参与不参与倍数的研究，是我们主观的决定。但不管如何，0的确是任何自然数的倍数（0倍）。

#42

该回复于2009-09-01 10:41:45被版主删除

#43

呵呵 39楼...

#44

引用 14 楼 wizard2215 的回复:

类似于八楼的做法，例如n=7 取{1，10，100，1000，10000，100000} 他们对7的余数{1，3，2，6，4，5}，只要从这个集合里面找出前几个数字相加可以等于7就可以了，那几个余数对应的原来的数相加，就是符合要求的最小的数。比如说7是1+6对应原来的数字1+1000=1001。用这种方法应该可以。

万一怎么相加都不能等于n那么就不行了,但我不能证明是否有这个可能性
无论如何这也是一个很好的想法

#45

学习   顶了

#46

#include <math.h>
#include <string>
#include <iostream>
#include <vector>

// 以下函数尝试找出一个全部由1、0组成，并能被n整除的自然数。结果存入strOut。
// 算法过程是生成比n大的所有全部由1、0组成的数，并逐个判断。
// 此算法仍有很大优化的余地，比如用bitset代替vector，排除素数解，跳过整数倍等等。
// 考虑到代码长度及可读性，以及本题的意义和规模，再进行优化是没有必要的。
// 经测试，全局优化编译的版本，在2.1GHz的CPU上运行结果如下：
// 1至998：12.9879s（注：999的解超过30位，未能得出结果）
int Test( unsigned int n, std::string &strOut )
{
	// 定义存放大数数组的容器及迭代器
	std::vector<unsigned char> vecMul;
	std::vector<unsigned char>::iterator iCurBit;
	std::vector<unsigned char>::reverse_iterator riCurBit;
	// nStartBit为给定整数的位数+1，即最小可能解的位数
	unsigned int nDividend, nStartBit =
		(unsigned int)floor( log10( (float)n ) + 1.0f ) + 1;
	// vecMul以数组形式存放解，头部为低位，尾部为高位，赋初值为100...
	vecMul.resize( nStartBit, 0 );
	*vecMul.rbegin() = 1;
	// 大循环逐个生成可能的解，并判断是否能被给定数整除。解超过xx位视为无解
	for ( nDividend = 1; nDividend != 0 && vecMul.size() < 28; *iCurBit = 1 )
	{	// 下面的循环用于计算数组除法，原理与手算法类似
		for( nDividend = 0, riCurBit = vecMul.rbegin();
			riCurBit < vecMul.rend(); nDividend %= n )
			// nDividend为被除数和余数
			for ( unsigned int nDividendBit = (unsigned int)floor( log10(
				(float)nDividend ) + 1.0f ); nDividendBit < nStartBit &&
				riCurBit < vecMul.rend(); ++nDividendBit, ++riCurBit )
				// 在这一步中，上一次除得的余数和所给数接下来的位再组成被除数
				nDividend = nDividend * 10 + *riCurBit;
		// 当余数为0即表示已得出答案
		if ( nDividend == 0 )
			// 将数组中每一个数变为字符，输出到参数字串对象中
			for ( strOut.clear(), riCurBit = vecMul.rbegin();
				riCurBit < vecMul.rend(); ++riCurBit )
				strOut.push_back( *riCurBit + '0' );
		// 生成下一个全由1、0组成的数，原理和2进制数进位法相同
		for ( iCurBit = vecMul.begin(); iCurBit != vecMul.end() &&
		// 从低向高找到第一个0，将其左边的数全部置0，然后将其至1即完成进位
			*iCurBit == 1; *(iCurBit++) = 0 );
		// 如果一直到最高位都为1，则为数组增加一位。
		if ( iCurBit == vecMul.end() )
			iCurBit = vecMul.insert( vecMul.end(), 1 );
	}
	return nDividend;
}

// 以下为主函数及测试代码，结构简单，不再描述
void main( int argc, char* argv[] )
{
	std::string strResult;
	for ( int i = 1; i < 999; ++i )
		if ( 0 == Test( i, strResult ) )
			std::cout << i << " ==> " << strResult << std::endl;
}

#47

引用 40 楼 chiwenzi 的回复:

10000 ==> 100000
其实10000本身就满足条件了，1倍也是倍数啊。

这道题目没有说明m是否可能等于n，我认为不可以。当然，这是很无所谓的事。

引用 41 楼 chiwenzi 的回复:

0参与不参与倍数的研究，是我们主观的决定。但不管如何，0的确是任何自然数的倍数（0倍）。

在某种程序上0可以视为任何非0自然数的倍数，但是请注意，0绝对不能是0的倍数。这在数学上没有意义。

#48

这道题目没有说明m是否可能等于n，我认为不可以。当然，这是很无所谓的事。
=================
在某种程序上0可以视为任何非0自然数的倍数，但是请注意，0绝对不能是0的倍数。这在数学上没有意义。
=================
首先说1倍是无所谓的事，这就说明你完全不懂数学。其次从说0绝不是0的倍数这点上来看，很显然，你也完全没有弄懂什么是倍数。
数学辞典（吉林教育出版社）里对于倍数的定义如下：
某整数的整数倍称为原数的倍数，亦即，a*n=b(n是整数)，b是a的倍数(n倍)，而a是b的约数。例如：12是3的倍数，3是12的约数。
0*0=0，0*1=0，0*2=0，。。。0*x=0
0是本身的任意倍数，这完全不是没有意义。可以是0倍、1倍、。。。。。x倍。

#49

0的倍数只有0，fireseed同学明白了吗？

#50

对于数学来说是绝对不可以说出“无所谓”这三个字的