求由0和1构成的最小十进制正整数，其是指定正整数的倍数

gxqcn

可否针对 $10^k-1$ 整数倍的数采用特殊的加速算法？ $N=(10^k-1)/3$, $M=(10^(3k)-1)/9$ $N=(10^k-1)$, $M=(10^(9k)-1)/9$ $N=3(10^k-1)$, $M=(10^(9k+1)-1)/9 - 10^(7k)$ $N=9(10^k-1)$, $M=(10^(9k+1)-1)/9 - 10^k$

mathe

应该可以,但是不排除还存在其它超过64比特的值

gxqcn

综合 31# 发现的规律，以及 32# 的忠告， 将代码最终修订如下：

1. // http://bbs.emath.ac.cn/viewthread.php?tid=1689&page=4&fromuid=8#pid21134
3. #include <iostream>
4. #include <ctime>
6. #include <vector>
7. #include <map>
8. #include <algorithm>
9. using namespace std;
12. typedef unsigned int UINT32, *PUINT32;
13. typedef unsigned __int64 UINT64, *PUINT64;
15. typedef vector< UINT32 > U32_VECTOR;
16. typedef vector< UINT64 > U64_VECTOR;
17. typedef map< UINT32, UINT32 > KEY_INDEX_MAP;
18. typedef KEY_INDEX_MAP::value_type MVT;
20. #ifndef UInt32x32To64
21. # define UInt32x32To64(a, b) ((UINT64)(((UINT64)(a)) * ((UINT64)(b))))
22. #endif
24. #define FAST_SIZE 36
26. const UINT32 FAST_N[FAST_SIZE] = { 3, 9, 27, 33, 81, 99, 297, 333, 891, 999, 2997, 3333, 8991, 9999, 29997, 33333, 89991, 99999, 299997, 333333, 899991, 999999, 2999997, 3333333, 8999991, 9999999, 29999997, 33333333, 89999991, 99999999, 299999997, 333333333, 899999991, 999999999, 2999999997, 3333333333 };
27. const UINT32 FAST_M[FAST_SIZE] = { 3, 9, (7<<16)|10, 6, (1<<16)|10, 18, (14<<16)|19, 9, (2<<16)|19, 27, (21<<16)|28, 12, (3<<16)|28, 36, (28<<16)|37, 15, (4<<16)|37, 45, (35<<16)|46, 18, (5<<16)|46, 54, (42<<16)|55, 21, (6<<16)|55, 63, (49<<16)|64, 24, (7<<16)|64, 72, (56<<16)|73, 27, (8<<16)|73, 81, (63<<16)|82, 30 };
29. char szResult[128];
32. __declspec(naked)
33. UINT32 DivMod5( UINT32& n )
34. {
35. __asm
36. {
37. mov ecx, dword ptr[esp + 0x04];
39. mov edx, dword ptr[ecx];
40. mov eax, 0xCCCCCCCD;
41. push edx;
43. mul edx;
44. shr edx, 2;
45. mov dword ptr[ecx], edx;
47. lea edx, [edx + 0x04*edx];
49. pop eax;
50. sub eax, edx;
52. ret;
53. }
54. }
57. __declspec(naked)
58. UINT32 DivMod10( UINT32& n )
59. {
60. __asm
61. {
62. mov ecx, dword ptr[esp + 0x04];
64. mov edx, dword ptr[ecx];
65. mov eax, 0xCCCCCCCD;
66. push edx;
68. mul edx;
69. shr edx, 3;
70. mov dword ptr[ecx], edx;
72. imul edx, 10;
74. pop eax;
75. sub eax, edx;
77. ret;
78. }
79. }
82. const char * GetMin01( UINT32 n )
83. {
84. char * p = szResult;
86. UINT32 i=0, j=0, d, ten, bits, index, size0, size1;
87. UINT32 key;
88. UINT64 value;
90. U32_VECTOR vKey;
91. U64_VECTOR vValue;
92. KEY_INDEX_MAP mKeyIndex;
94. KEY_INDEX_MAP::iterator it;
96. *( p += 127 ) = '\0';
98. // if ( 0 == n ) return p;
100. while ( 0 == ( 1 & n ))
101. {
102. ++i; //times of prime 2
103. n >>= 1;
104. }
106. while ( 0 == ( d = DivMod5( n )))
107. {
108. ++j; //times of prime 5
109. }
110. n = n * 5 + d;
112. if ( i < j ) i = j; //max times of prime 2 and prime 5
113. memset( p -= i, '0', i * sizeof(char));
115. i = n;
116. j = 0;
117. while (( d = DivMod10( i )) <= 1 )
118. {
119. ++j;
121. *(--p) = '0' + d;
122. if ( 0 == i )
123. {
124. return p;
125. }
126. }
127. p += j;
129. //special case
130. const UINT32 * pFast = lower_bound( FAST_N, FAST_N + FAST_SIZE, n );
131. if ( FAST_N + FAST_SIZE != pFast && n == *pFast )
132. {
133. d = FAST_M[ pFast - FAST_N ];
134. i = d & 0xFFFF;
135. j = d >> 16;
137. memset( p -= i, '1', i * sizeof(char));
138. if ( 0 != j )
139. {
140. *( p + i - j - 1 ) = '0';
141. }
143. return p;
144. }
146. vKey.push_back( 0 );
147. vValue.push_back( 0 );
148. mKeyIndex.insert( MVT( 0, index = 0 ));
150. vKey.push_back( 1 );
151. vValue.push_back( 1 );
152. mKeyIndex.insert( MVT( 1, ++index ));
154. for ( bits=1, ten=10%n, size1=size0=vKey.size(); ; )
155. {
156. for ( i=1; size0!=i; ++i )
157. {
158. d = (UINT32)( UInt32x32To64( vKey[i], ten ) % n );
159. if ( mKeyIndex.end() != ( it = mKeyIndex.find( n - d )))
160. {
161. value = vValue[(*it).second];
162. do
163. {
164. *(--p) = '0' + ( 1 & value );
165. value >>= 1;
166. } while( 0 != --bits );
168. value = vValue[i];
169. do
170. {
171. *(--p) = '0' + ( 1 & value );
172. } while( 0 != ( value >>= 1 ));
174. return p;
175. }
176. }
178. for ( i=1; size1!=i; ++i )
179. {
180. d = (UINT32)( UInt32x32To64( vKey[i], ten ) % n );
181. value = vValue[i] << bits;
183. for ( j=0; size0!=j; ++j )
184. {
185. if ( key = vKey[j] + d, key < d || key >= n )
186. {
187. key -= n;
188. }
189. if ( mKeyIndex.end() == mKeyIndex.find( key ))
190. {
191. vKey.push_back( key );
192. vValue.push_back( vValue[j] | value );
193. mKeyIndex.insert( MVT( key, ++index ));
194. }
195. }
196. }
198. if ( size1 == size0 )
199. {
200. bits <<= 1;
201. ten = (UINT32)( UInt32x32To64( ten, ten ) % n );
202. }
203. else
204. {
205. ++bits;
206. ten = (UINT32)( UInt32x32To64( ten, 10 ) % n );
207. }
209. size0 = vKey.size();
210. size1 = ( bits < 16 ) ? size0 : 2;
211. }
213. return p;
214. }
217. int main( void )
218. {
219. UINT32 n;
220. const char * p;
222. while( 1 )
223. {
224. cout << "N=";
225. cin >> n;
227. if( 0 == n )
228. {
229. break;
230. }
232. clock_t start=clock();
233. p = GetMin01( n );
234. clock_t end=clock();
236. cout << p << "\n";
237. cout<< "Total cost " << end-start << "ms" << "\n" << endl;
238. }
240. return 0;
241. }

复制代码

（由于效率已比较高了，且排除了bug的可能，所以上述代码我将不再会去修改了。） 在 VC6.0 环境下编译得到： search_pid21134.zip (24.4 KB, 下载次数: 12)

2009-8-18 09:18 上传

点击文件名下载附件
VC6.0 编译

运行示例：

N=699999993 111111111111111111111111111111111111111111111111111111111111111111111111 Total cost 19906ms N=