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

gxqcn · 发表于 2009-8-11 08:05:11

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

在十进制中，给定正整数N（0<N<10^8），求最小的正整数M，使得M可被N整除，且M每个数字为0或1之一。

要求：
1、编程环境（包括使用第三方类库）不限；
2、对于任意指定的N或连续的N，尽可能快地输出对应的M。

额外奖励：最先公布出在 0<N<10⁸ 范围内对应 M 的最大值，经验证无误后，本人将额外转赠100分。

擂台背景：有人在 CSDN 上提出该问题，但截止到目前似乎还没有比较理想的算法，所以放在本论坛里继续讨论；为了方便讨论，特对范围作了下限定。

mathe · 发表于 2009-8-11 08:20:13

这是我现在的版本,在输入数据小于32比特时都没有问题,而且速度都很快:

#include <map>
#include <iostream>
#include <ctime>
#include <vector>
#include <math.h>
#include <assert.h>
using namespace std;
typedef long long itype;
typedef map<itype, int> Vmap;
Vmap the_map;
Vmap next_map;
Vmap *cur_map,*prev_map,*tmp_map;
vector<itype> tens;
void dumpvalue(itype key,itype n,int maxbit)
{
Vmap::const_iterator cit;
cit=cur_map->find(key);
assert(cit!=cur_map->end());
int i;
for(i=cit->second;i<maxbit;i++){
cout<<0;
}
cout<<1;
key-=tens[cit->second];
if(key<0)key+=n;
if(key>0){
dumpvalue(key,n,cit->second-1);
}else{
for(i=0;i<cit->second;i++){
cout<<0;
}
}
}
bool cmpit(Vmap::const_iterator it1, Vmap::const_iterator it2,itype n)
{
if(it1->second<it2->second)
return true;
if(it1->second>it2->second)
return false;
itype key1=(it1->first-tens[it1->second]);
itype key2=(it2->first-tens[it2->second]);
if(key1<0)key1+=n;
if(key2<0)key2+=n;
if(key1==0)return true;
if(key2==0)return false;
it1=cur_map->find(key1);
it2=cur_map->find(key2);
return cmpit(it1,it2,n);
}
int main()
{
itype n;
while(1){
cout<<"N=";
cin>>n;
if(n<=0)
break;
clock_t start=clock();
int c2=0,c5=0;
while(n%2==0){c2++;n/=2;}//times of prime 2
while(n%5==0){c5++;n/=5;}//times of prime 5
if(c5<c2)c5=c2;//max times of prime 2 and prime 5
int i;
if(n==1){
cout<<1;
for(i=0;i<c5;i++){cout<<0;}
cout<<endl;
goto output_time;
}
//special case that n+1 is 10^h
itype m=n+1;
int c10=0;
while(m%10==0){m/=10,c10++;}
if(m==1){
for(i=0;i<c10;i++){cout<<111111111;}
for(i=0;i<c5;i++){cout<<0;}
cout<<endl;
goto output_time;
}
int b=(int)sqrt((double)n)+1;
the_map.clear();
tens.clear();
the_map[1]=0;///The first bit 1 is the 0'th bit
cur_map=&the_map;
prev_map=&next_map;
tens.push_back(1);
tens.push_back(10%n);
bool find=false;
itype find_key;
itype mkey;
Vmap::const_iterator bit;
for(i=1;!find;i++){
m=tens[i];
Vmap::iterator it;
Vmap::const_iterator cit;
tmp_map=cur_map;cur_map=prev_map;prev_map=tmp_map;//swap two maps
cur_map->clear();//reset current map
it=prev_map->find(m);
if(it==prev_map->end()){//add when 10^i is new
cur_map->insert(pair<itype,int>(m,i));
}
for(cit=prev_map->begin();cit!=prev_map->end();++cit){
itype key=cit->first;
cur_map->insert(pair<itype,int>(key,cit->second));
key=(key+m)%n;
it=prev_map->find(key);
if(it==prev_map->end()){
cur_map->insert(pair<itype,int>(key,i));
if(key==0){
find_key=key;
find=true;
}
}
}
itype nm=(m*10)%n;
tens.push_back(nm);
if(!find&&cur_map->size()>=b){
nm=n-nm;
itype mink=-1,mkey2;
for(cit=cur_map->begin();cit!=cur_map->end();++cit){
itype nkey=cit->first;
nkey=(itype)((nkey*(long long)nm)%n);
it=cur_map->find(nkey);
if(it!=cur_map->end()){
if(mink==-1||cmpit(cit,bit,n)){
mink=cit->first;
mkey2=nkey;
bit=cit;
}
}
}
if(mink>=0){
find_key=mink;
mkey=mkey2;
find=true;
}
}
}
if(find_key==0){
dumpvalue(0,n,-1);
}else{
dumpvalue(find_key,n,-1);
dumpvalue(mkey,n,i-1);
}
for(i=0;i<c5;i++){cout<<0;}
cout<<endl;
output_time:
clock_t end=clock();
cout<<"Total cost "<<end-start<<"ms"<<endl;
}
return 0;
}

复制代码

mathe · 发表于 2009-8-11 08:21:58

至于你那个额外奖励,比较简单

N=99999999
M=111111111111111111111111111111111111111111111111111111111111111111111111

gxqcn · 发表于 2009-8-11 08:33:44

看样子 mathe 已对本问题有所研究了。

我抽空把我的一个初步想法实现后再对比看看。

无心人 · 发表于 2009-8-11 19:42:03

显然，个位必定是1

从个位向高位推吧？

gxqcn · 发表于 2009-8-13 10:25:08

我昨天调试了一版，也是通过 map 实现的，但测试下来效率并不高。
于是，潜心研究 mathe 的代码，想到了对自己的一优化算法。

今天，我重新改写算法，结合采用 STL 里的 vector 和 set 容器（不再用 map），测试下来效率非常高

与 2# 同样的，输入数据可为任意小于32比特的正整数。

代码如下：

// http://bbs.emath.ac.cn/viewthread.php?tid=1689&page=1&fromuid=8#pid21060
#include <iostream>
#include <ctime>
#include <vector>
#include <set>
using namespace std;
typedef unsigned int UINT32, *PUINT32;
typedef unsigned __int64 UINT64, *PUINT64;
typedef struct node
{
UINT32 key;
UINT64 value;
}NODE;
typedef vector< NODE > NODE_VECTOR;
typedef set< UINT32 > KEY_SET;
#ifndef UInt32x32To64
# define UInt32x32To64(a, b) (((UINT64)(a)) * (b))
#endif
char szResult[128];
const char * GetMin01( UINT32 n )
{
char * p = szResult;
UINT32 i=0, j=0, d, ten, bits, size;
NODE info;
UINT32 key;
UINT64 value;
NODE_VECTOR vNode;
KEY_SET sKey;
NODE_VECTOR::iterator vIt1, vIt0;
*( p += 127 ) = '\0';
// if ( 0 == n ) return p;
while(0==n%2){++i;n/=2;}//times of prime 2
while(0==n%5){++j;n/=5;}//times of prime 5
if(i<j){i=j;}//max times of prime 2 and prime 5
memset( p -= i, '0', i * sizeof(char));
if ( 1 == n )
{
*(--p) = '1';
return p;
}
//special case that n+1 is 10^j
i = n + 1;
j = 0;
while(0==i%10){i/=10;++j;}
if ( 1 == i )
{
j *= 9;
memset( p -= j, '1', j * sizeof(char));
return p;
}
memset( &info, 0, sizeof( info ));
vNode.push_back( info );
sKey.insert( info.key );
info.value = info.key = 1;
vNode.push_back( info );
sKey.insert( info.key );
for ( bits=1, ten=10%n; ; bits<<=1 )
{
for ( vIt1 = vNode.begin(); vNode.end() != ++vIt1; )
{
key = n - (UINT32)( UInt32x32To64( vIt1->key, ten ) % n );
if ( sKey.end() != sKey.find( key ))
{
for ( vIt0 = vNode.begin(); ++vIt0, key != vIt0->key; )
;
value = vIt0->value;
do
{
*(--p) = ( 1 & value ) ? '1' : '0';
value >>= 1;
} while( 0 != --bits );
do
{
*(--p) = ( 1 & vIt1->value ) ? '1' : '0';
} while( 0 != ( vIt1->value >>= 1 ));
return p;
}
}
for ( i = 1, size = vNode.size(); size != i; ++i )
{
d = (UINT32)( UInt32x32To64( vNode[i].key, ten ) % n );
value = vNode[i].value << bits;
for ( j = 0; size != j; ++j )
{
key = vNode[j].key;
if (( key += d ) >= n )
{
key -= n;
}
if ( sKey.end() == sKey.find( key ))
{
sKey.insert( info.key = key );
info.value = vNode[j].value | value;
vNode.push_back( info );
}
}
}
ten = (UINT32)( UInt32x32To64( ten, ten ) % n );
}
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;
}

复制代码

gxqcn · 发表于 2009-8-13 11:27:33

当输入N=4294967291时（32位内的最大素数），
结果为1011101001001001001010000111001，
2# 耗时327ms，6#耗时82ms

其它输入，基本持平，两者各有千秋。

但我的程序在 N=4294967279 时会进入“长考”

，
经 debug，发现它将试图构造一个超大的表，暂不知如何解决。

mathe 的程序则可顺利通过，真不知其玄妙在哪里？
（其实，mathe 的算法，我主要是阅读在CSDN 上的描述方面，代码并未细读）

mathe · 发表于 2009-8-13 21:14:39

这个题目要首先考虑控制空间复杂度.

gxqcn · 发表于 2009-8-15 22:18:13

这几天空闲时间我一直在琢磨这个问题，如何对自己现有的程序进行优化？如何解决空间问题？

现在终于调试好了，时间和空间的效率都非常理想：

// http://bbs.emath.ac.cn/viewthread.php?tid=1689&page=1&fromuid=8#pid21085
#include <iostream>
#include <ctime>
#include <vector>
#include <map>
using namespace std;
typedef unsigned int UINT32, *PUINT32;
typedef unsigned __int64 UINT64, *PUINT64;
typedef struct node
{
UINT32 key;
UINT64 value;
}NODE;
typedef vector< NODE > NODE_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
char szResult[128];
const char * GetMin01( UINT32 n )
{
char * p = szResult;
UINT32 i=0, j=0, d, ten, bits, index, size0, size1;
UINT32 key;
UINT64 value;
NODE info;
NODE_VECTOR vNode;
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 == n % 5 )
{
++j; //times of prime 5
n /= 5;
}
if ( i < j ) i = j; //max times of prime 2 and prime 5
memset( p -= i, '0', i * sizeof(char));
if ( 1 == n )
{
*(--p) = '1';
return p;
}
//special case that n+1 is 10^j
i = n + 1;
j = 0;
while ( 0 == i % 10 )
{
++j;
i /= 10;
}
if ( 1 == i )
{
j *= 9;
memset( p -= j, '1', j * sizeof(char));
return p;
}
switch( n )
{
case 3:
case 37: n = 111;
break;
case 7:
case 13: n = 1001;
break;
case 337: n = 1011;
break;
case 367: n = 1101;
break;
default:
break;
}
i = n;
j = 0;
while (( d = i % 10 ) <= 1 )
{
*(--p) = '0' + d;
if ( 0 == ( i /= 10 ))
{
return p;
}
++j;
}
p += j;
const UINT32 INIT4BITS[] = { 0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, };
for ( i=0; 16!=i; ++i )
{
info.key = INIT4BITS[i] % n;
info.value = i;
vNode.push_back( info );
mKeyIndex.insert( MVT( info.key, i ));
}
index = i - 1;
for ( bits=4, ten=10000%n, size1=size0=vNode.size(); ; )
{
for ( i=1; size0!=i; ++i )
{
d = (UINT32)( UInt32x32To64( vNode[i].key, ten ) % n );
if ( mKeyIndex.end() != ( it = mKeyIndex.find( n - d )))
{
value = vNode[(*it).second].value;
do
{
*(--p) = '0' + ( 1 & value );
value >>= 1;
} while( 0 != --bits );
value = vNode[i].value;
do
{
*(--p) = '0' + ( 1 & value );
} while( 0 != ( value >>= 1 ));
return p;
}
}
for ( i=1; size1!=i; ++i )
{
d = (UINT32)( UInt32x32To64( vNode[i].key, ten ) % n );
value = vNode[i].value << bits;
for ( j=0; size0!=j; ++j )
{
key = vNode[j].key + d;
if ( key < d || key >= n )
{
key -= n;
}
if ( mKeyIndex.end() == mKeyIndex.find( key ))
{
mKeyIndex.insert( MVT( info.key = key, ++index ));
info.value = vNode[j].value | value;
vNode.push_back( info );
}
}
}
if ( size1 == size0 )
{
bits <<= 1;
ten = (UINT32)( UInt32x32To64( ten, ten ) % n );
}
else
{
++bits;
ten = (UINT32)( UInt32x32To64( ten, 10 ) % n );
}
size0 = vNode.size();
if ( UInt32x32To64( size0, size0 ) <= (UINT64)n )
{
size1 = size0;
}
else
{
size1 = 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，直到刚刚才debug出问题所在，郁闷死了。

而问题出在 No.161 行，之前少加了“key < d ||”（高手肯定知道它是在判定什么的吧？），
导致在输入较大的 N 时，因未判定溢出而得不到正确结果。

现在的程序效率比 mathe 的更高（当 N 非常大时），因为它无需将数据在几个 map 间进行倒腾。

gxqcn · 发表于 2009-8-15 22:26:59

另外，上述程序的 181、182 和 192 行可以对应修改，比如改成：

// ...
if ( size1 == size0 )
{
bits <<= 1;
ten = (UINT32)( UInt32x32To64( ten, ten ) % n );
}
else
{
bits += 4;
ten = (UINT32)( UInt32x32To64( ten, 10000 ) % n );
}
size0 = vNode.size();
if ( UInt32x32To64( size0, size0 ) <= (UINT64)n )
{
size1 = size0;
}
else
{
size1 = 16;
}
}
return p;
}

复制代码

但实际测试下来的结果看，bits 逐步递增效果更好（我仅测了几个非常大的素数）。

账号		自动登录	找回密码
密码			欢迎注册

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

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

评分

评分

发布我的版本（曾参考了 mathe 的）