问题转换为求1跟0组成的最小自然数,使其对N取余结果为零。
查找关键是创建一个跟N一样大小的辅助数组,来存储取余结果等于数组下标值的1、0组成的最小自然数。
然后逐渐增大work的倍数,直至找到这个自然数。
#include <iostream>
#include <windows.h>
using namespace std;
#define T INT64
T search(int a)
{
T * p=new T[a];
for(int i=0;i!=a;++i)
p[i]=-1;
T work=1;
while(p[0]==-1)
{
int temp=work%a;
if(p[temp]==-1)
p[temp]=work;
for(int i=0;i!=a;++i)
{
if(p[i]!=-1&&p[i]<work)
{
int t=(temp+i)%a;
if(p[t]==-1)
p[t]=work+p[i];
}
}
work*=10;
}
T result=p[0];
delete []p;
return result;
}
void main()
{
int test;
while(1)
{
cin>>test;
T result=search(test);
cout<<result/test<<"*"<<test<<"="<<result<<endl;
}
}