求由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
   
2. 
   
3. #include <iostream>
   
4. #include <ctime>
   
5. 
   
6. #include <vector>
   
7. #include <map>
   
8. #include <algorithm>
   
9. using namespace std;
   
10. 
    
11. 
    
12. typedef unsigned int UINT32, *PUINT32;
    
13. typedef unsigned __int64 UINT64, *PUINT64;
    
14. 
    
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;
    
19. 
    
20. #ifndef UInt32x32To64
    
21. #     define UInt32x32To64(a, b)    ((UINT64)(((UINT64)(a)) * ((UINT64)(b))))
    
22. #endif
    
23. 
    
24. #define FAST_SIZE                    36
    
25. 
    
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 };
    
28. 
    
29. char szResult[128];
    
30. 
    
31. 
    
32. __declspec(naked)
    
33. UINT32 DivMod5( UINT32& n )
    
34. {
    
35.     __asm
    
36.     {
    
37.         mov     ecx, dword ptr[esp + 0x04];
    
38. 
    
39.         mov     edx, dword ptr[ecx];
    
40.         mov     eax, 0xCCCCCCCD;
    
41.         push    edx;
    
42. 
    
43.         mul     edx;
    
44.         shr     edx, 2;
    
45.         mov     dword ptr[ecx], edx;
    
46. 
    
47.         lea     edx, [edx + 0x04*edx];
    
48. 
    
49.         pop     eax;
    
50.         sub     eax, edx;
    
51. 
    
52.         ret;
    
53.     }
    
54. }
    
55. 
    
56. 
    
57. __declspec(naked)
    
58. UINT32 DivMod10( UINT32& n )
    
59. {
    
60.     __asm
    
61.     {
    
62.         mov     ecx, dword ptr[esp + 0x04];
    
63. 
    
64.         mov     edx, dword ptr[ecx];
    
65.         mov     eax, 0xCCCCCCCD;
    
66.         push    edx;
    
67. 
    
68.         mul     edx;
    
69.         shr     edx, 3;
    
70.         mov     dword ptr[ecx], edx;
    
71. 
    
72.         imul    edx, 10;
    
73. 
    
74.         pop     eax;
    
75.         sub     eax, edx;
    
76. 
    
77.         ret;
    
78.     }
    
79. }
    
80. 
    
81. 
    
82. const char * GetMin01( UINT32 n )
    
83. {
    
84.     char * p = szResult;
    
85. 
    
86.     UINT32 i=0, j=0, d, ten, bits, index, size0, size1;
    
87.     UINT32 key;
    
88.     UINT64 value;
    
89. 
    
90.     U32_VECTOR vKey;
    
91.     U64_VECTOR vValue;
    
92.     KEY_INDEX_MAP mKeyIndex;
    
93. 
    
94.     KEY_INDEX_MAP::iterator it;
    
95. 
    
96.     *( p += 127 ) = '\0';
    
97. 
    
98. //  if ( 0 == n ) return p;
    
99. 
    
100.     while ( 0 == ( 1 & n ))
     
101.     {
     
102.         ++i;    //times of prime 2
     
103.         n >>= 1;
     
104.     }
     
105. 
     
106.     while ( 0 == ( d = DivMod5( n )))
     
107.     {
     
108.         ++j;    //times of prime 5
     
109.     }
     
110.     n = n * 5 + d;
     
111. 
     
112.     if ( i < j ) i = j; //max times of prime 2 and prime 5
     
113.     memset( p -= i, '0', i * sizeof(char));
     
114. 
     
115.     i = n;
     
116.     j = 0;
     
117.     while (( d = DivMod10( i )) <= 1 )
     
118.     {
     
119.         ++j;
     
120. 
     
121.         *(--p) = '0' + d;
     
122.         if ( 0 == i )
     
123.         {
     
124.             return p;
     
125.         }
     
126.     }
     
127.     p += j;
     
128. 
     
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;
     
136. 
     
137.         memset( p -= i, '1', i * sizeof(char));
     
138.         if ( 0 != j )
     
139.         {
     
140.             *( p + i - j - 1 ) = '0';
     
141.         }
     
142. 
     
143.         return p;
     
144.     }
     
145. 
     
146.     vKey.push_back( 0 );
     
147.     vValue.push_back( 0 );
     
148.     mKeyIndex.insert( MVT( 0, index = 0 ));
     
149. 
     
150.     vKey.push_back( 1 );
     
151.     vValue.push_back( 1 );
     
152.     mKeyIndex.insert( MVT( 1, ++index ));
     
153. 
     
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 );
     
167. 
     
168.                 value = vValue[i];
     
169.                 do
     
170.                 {
     
171.                     *(--p) = '0' + ( 1 & value );
     
172.                 } while( 0 != ( value >>= 1 ));
     
173. 
     
174.                 return p;
     
175.             }
     
176.         }
     
177. 
     
178.         for ( i=1; size1!=i; ++i )
     
179.         {
     
180.             d = (UINT32)( UInt32x32To64( vKey[i], ten ) % n );
     
181.             value = vValue[i] << bits;
     
182. 
     
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.         }
     
197. 
     
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.         }
     
208. 
     
209.         size0 = vKey.size();
     
210.         size1 = ( bits < 16 ) ? size0 : 2;
     
211.     }
     
212. 
     
213.     return p;
     
214. }
     
215. 
     
216. 
     
217. int main( void )
     
218. {
     
219.     UINT32 n;
     
220.     const char * p;
     
221. 
     
222.     while( 1 )
     
223.     {
     
224.         cout << "N=";
     
225.         cin >> n;
     
226. 
     
227.         if( 0 == n )
     
228.         {
     
229.             break;
     
230.         }
     
231. 
     
232.         clock_t start=clock();
     
233.         p = GetMin01( n );
     
234.         clock_t end=clock();
     
235. 
     
236.         cout << p << "\n";
     
237.         cout<< "Total cost " << end-start << "ms" << "\n" << endl;
     
238.     }
     
239. 
     
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=