求出n的倍数m，要求m使用的不同数字最少，且最小。
一开始不知道怎么搜，因为不知道m由多少个不同的数字组成。
然后百度了一下，看到和数论有关。
m可能使用的数字的个数可能为一个或者两个
a,aa,aaa....n+1个a， 将这些数%n，那么肯定有两个余数相等，抽屉原理。那么这两个数相减，得到的数肯定是n的倍数，且这两个数由a和0组成。
所以就知道怎么搜了，先搜m由一个数组成的情况，如果不存在，那么就搜两个数组成的情况，要注意全部搜完，因为题目要求m最小。
#include <stdio.h>
#include <string.h>
#include <queue>
#include <iostream>
#include <string>
using namespace std;
struct node
{
int res;
string str;
};
bool vis[];;
int digit;
int cnt;
string ans;
bool find_; void bfs1(int n)
{
int res;
int k;
for(int i=; i<=; ++i)
{
k = ;
res = i % n;
memset(vis,,sizeof(vis));
while(!vis[res] && res!=)
{
vis[res] = true;
res = (res * + i) % n;
k++;
}
if(res==)
{
if(cnt==)
{
cnt = k;
digit = i;
}
else if(cnt>k)
{
cnt = k;
digit = i;
}
}
}
}
void bfs2(int i, int j,int n)
{
memset(vis,,sizeof(vis));
queue<node> q;
node cur,tmp;
if(i!=)
{
cur.res = i % n;
cur.str = (char)(i+'');
q.push(cur);
}
cur.res = j % n;
cur.str = (char)(j+'');
q.push(cur);
while(!q.empty())
{
cur = q.front(); q.pop();
if(cur.res ==)
{
if(!find_)
{
ans = cur.str;
find_ = true;
}
else if(cur.str.size() < ans.size())
ans = cur.str;
else if(cur.str.size()==ans.size() && cur.str < ans)
ans = cur.str;
return; }
if(find_ && cur.str.size() >= ans.size())
continue;
tmp.res = (cur.res * + i) % n;
if(!vis[tmp.res])
{
vis[tmp.res] = true;
tmp.str = cur.str + (char)(i+''); q.push(tmp);
}
tmp.res = (cur.res * + j) % n;
if(!vis[tmp.res])
{
vis[tmp.res] = true;
tmp.str = cur.str + (char)(j+'');
q.push(tmp);
}
}
} int main()
{
int n,i,j;
while(scanf("%d",&n),n)
{
find_ = false;
cnt = ;
bfs1(n);
if(cnt!=)
for(i=; i<cnt; ++i)
printf("%d",digit);
else
{
for(i=; i<=; ++i)
for(j=i+; j<=; ++j)
{
bfs2(i,j,n);
}
cout<<ans;
}
puts("");
}
}