input
n 不超过50个例子，n==0结束输入
Sample Input
7 15 16 101 0
output
最少个不同数字的n的倍数的x，若不同数字个数一样，输出最小的x
Sample Output
7 555 16 1111
根据数论里面的知识点：
对于任意的整数 n ，必然存在一个由不多于两个的数来组成的一个倍数。 因为 a ，aa ， aaa…… 取 n+1 个，则由鸽笼原理，必有两个模 n 余数相同，相减即得 n 的倍数 m 。而 m 只由 a 、 0 组成。
#include <bits/stdc++.h>
#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <cctype>
#include <string>
#include <bitset>
#define MAX 65600
#define LL long long
#define uint unsigned short
using namespace std;
int cas=,T,n;
struct node1
{
int i,r;
};
char v1[MAX][];
int bfs1()
{
int step=,d=;
queue<node1>q[];
memset(v1,,sizeof(v1[])*n);
for(int i=;i<;i++) { q[].push((node1){i,i%n});v1[i%n][i]=; }
while(!q[d].empty()) //两个队列bfs，一个队列存一步里面走的
{
while(!q[d].empty())
{
node1 u=q[d].front();q[d].pop();
if(u.r==)
{
for(int i=;i<step;i++) printf("%d",u.i);
printf("\n");
return ;
}
node1 v;
v.r=(u.r*+u.i)%n;
if(v1[v.r][u.i]) continue;
v.i=u.i;q[d^].push(v);
v1[v.r][u.i]=;
}
step++;
d^=;
}
return ;
}
struct node
{
uint r,i,a,b; //a,b是两个不同的数字且a<b<10,r是余数，i是当前取的数，输出时要用
int fa; //父结点，查找路径用
};
node q[MAX*];
char v[MAX][];
uint idx(uint &a,uint&b) { return (b*b-b)/+a; }
void init(int &end) //初始化队列,一次将所有的入队用的内存太多，也可以分成45次bfs()
{
for(int i=;i<;i++) //从小到大入队
{
int a=i/,b=i%; //a是个位，b是十位
if(a==b)//a，b相同时可以是550 551 552 553 554 556 557 558 559
{
for(int j=;j<;j++)
{
if(a==j) continue;
node&u=q[end];
u.i=i;u.r=i%n;
u.a=min(a,j);u.b=max(a,j);u.fa=-;
int id=idx(u.a,u.b);
v[a][id]=v[i][id]=;
end++;
// printf("%d %d %d %d %d\n",u.i,u.r,u.a,u.b,u.fa);
}
continue;
}
node&u=q[end]; //a,b不同时直接入队即可
u.i=i;u.r=i%n;
u.a=min(a,b);u.b=max(a,b);u.fa=-;
int id=idx(u.a,u.b);
v[a][id]=v[i][id]=;
end++;
// printf("%d %d %d %d %d\n",u.i,u.r,u.a,u.b,u.fa);
}
}
void print(int u)
{
if(q[u].fa==-) { printf("%d",q[u].i);return; }
print(q[u].fa);
printf("%d",q[u].i);
}
void bfs2()
{
memset(v,,sizeof(v[])*n);
int front=,end=;
init(end);
while(front<end)
{
node&u=q[end],&f=q[front];
int id=idx(f.a,f.b);
if(f.r==) { print(front);printf("\n");return; }
u.r=((int)f.r*+f.a)%n;
if(!v[u.r][id]) //加一位a
{
v[u.r][id]=; //刚开始错在这，没有标记，也是够傻了。。。而且还一直找不到。。。
u.a=f.a;u.b=f.b;u.fa=front;
u.i=f.a;
end++;
}
node&p=q[end];
p.r=((int)f.r*+f.b)%n;
if(!v[p.r][id]) //加一位b
{
v[p.r][id]==;
p.a=f.a;p.b=f.b;p.fa=front;
p.i=f.b;
end++;
}
front++;
// printf("%d %d\n",front,end);
}
}
int main()
{
//freopen("out","w",stdout);
//freopen("in","r",stdin);
//scanf("%d",&T);
while(scanf("%d",&n)==&&n)
//for(n=65535;n>0;n--)
{
if(bfs1()) continue;
bfs2();
}
//printf("time=%.3lf\n",(double)clock()/CLOCKS_PER_SEC);
return ;
}