$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$ 应该可以,但是不排除还存在其它超过64比特的值
最终版本
综合 31# 发现的规律，以及 32# 的忠告，将代码最终修订如下：//http://bbs.emath.ac.cn/viewthread.php?tid=1689&page=4&fromuid=8#pid21134
#include <iostream>
#include <ctime>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef unsigned int UINT32, *PUINT32;
typedef unsigned __int64 UINT64, *PUINT64;
typedef vector< UINT32 > U32_VECTOR;
typedef vector< UINT64 > U64_VECTOR;
typedef map< UINT32, UINT32 > KEY_INDEX_MAP;
typedef KEY_INDEX_MAP::value_type MVT;
#ifndef UInt32x32To64
# define UInt32x32To64(a, b) ((UINT64)(((UINT64)(a)) * ((UINT64)(b))))
#endif
#define FAST_SIZE 36
const UINT32 FAST_N = { 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 };
const UINT32 FAST_M = { 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 };
char szResult;
__declspec(naked)
UINT32 DivMod5( UINT32& n )
{
__asm
{
mov ecx, dword ptr;
mov edx, dword ptr;
mov eax, 0xCCCCCCCD;
push edx;
mul edx;
shr edx, 2;
mov dword ptr, edx;
lea edx, ;
pop eax;
sub eax, edx;
ret;
}
}
__declspec(naked)
UINT32 DivMod10( UINT32& n )
{
__asm
{
mov ecx, dword ptr;
mov edx, dword ptr;
mov eax, 0xCCCCCCCD;
push edx;
mul edx;
shr edx, 3;
mov dword ptr, edx;
imul edx, 10;
pop eax;
sub eax, edx;
ret;
}
}
const char * GetMin01( UINT32 n )
{
char * p = szResult;
UINT32 i=0, j=0, d, ten, bits, index, size0, size1;
UINT32 key;
UINT64 value;
U32_VECTOR vKey;
U64_VECTOR vValue;
KEY_INDEX_MAP mKeyIndex;
KEY_INDEX_MAP::iterator it;
*( p += 127 ) = '\0';
//if ( 0 == n ) return p;
while ( 0 == ( 1 & n ))
{
++i; //times of prime 2
n >>= 1;
}
while ( 0 == ( d = DivMod5( n )))
{
++j; //times of prime 5
}
n = n * 5 + d;
if ( i < j ) i = j; //max times of prime 2 and prime 5
memset( p -= i, '0', i * sizeof(char));
i = n;
j = 0;
while (( d = DivMod10( i )) <= 1 )
{
++j;
*(--p) = '0' + d;
if ( 0 == i )
{
return p;
}
}
p += j;
//special case
const UINT32 * pFast = lower_bound( FAST_N, FAST_N + FAST_SIZE, n );
if ( FAST_N + FAST_SIZE != pFast && n == *pFast )
{
d = FAST_M[ pFast - FAST_N ];
i = d & 0xFFFF;
j = d >> 16;
memset( p -= i, '1', i * sizeof(char));
if ( 0 != j )
{
*( p + i - j - 1 ) = '0';
}
return p;
}
vKey.push_back( 0 );
vValue.push_back( 0 );
mKeyIndex.insert( MVT( 0, index = 0 ));
vKey.push_back( 1 );
vValue.push_back( 1 );
mKeyIndex.insert( MVT( 1, ++index ));
for ( bits=1, ten=10%n, size1=size0=vKey.size(); ; )
{
for ( i=1; size0!=i; ++i )
{
d = (UINT32)( UInt32x32To64( vKey, ten ) % n );
if ( mKeyIndex.end() != ( it = mKeyIndex.find( n - d )))
{
value = vValue[(*it).second];
do
{
*(--p) = '0' + ( 1 & value );
value >>= 1;
} while( 0 != --bits );
value = vValue;
do
{
*(--p) = '0' + ( 1 & value );
} while( 0 != ( value >>= 1 ));
return p;
}
}
for ( i=1; size1!=i; ++i )
{
d = (UINT32)( UInt32x32To64( vKey, ten ) % n );
value = vValue << bits;
for ( j=0; size0!=j; ++j )
{
if ( key = vKey + d, key < d || key >= n )
{
key -= n;
}
if ( mKeyIndex.end() == mKeyIndex.find( key ))
{
vKey.push_back( key );
vValue.push_back( vValue | value );
mKeyIndex.insert( MVT( key, ++index ));
}
}
}
if ( size1 == size0 )
{
bits <<= 1;
ten = (UINT32)( UInt32x32To64( ten, ten ) % n );
}
else
{
++bits;
ten = (UINT32)( UInt32x32To64( ten, 10 ) % n );
}
size0 = vKey.size();
size1 = ( bits < 16 ) ? size0 : 2;
}
return p;
}
int main( void )
{
UINT32 n;
const char * p;
while( 1 )
{
cout << "N=";
cin >> n;
if( 0 == n )
{
break;
}
clock_t start=clock();
p = GetMin01( n );
clock_t end=clock();
cout << p << "\n";
cout<< "Total cost " << end-start << "ms" << "\n" << endl;
}
return 0;
}（由于效率已比较高了，且排除了bug的可能，所以上述代码我将不再会去修改了。）
在 VC6.0 环境下编译得到：
运行示例：N=699999993
111111111111111111111111111111111111111111111111111111111111111111111111
Total cost 19906ms
N=