转：http://blog.csdn.net/wangjian8006/article/details/7460523
(比较好的记录路径方案)
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<string> #define N 1000005
#define M 9
#define mod 1000000007
//#define p 10000007
#define mod2 1000000000
#define ll long long
#define LL long long
#define eps 1e-6
#define inf 1000000
#define maxi(a,b) (a)>(b)? (a) : (b)
#define mini(a,b) (a)<(b)? (a) : (b) using namespace std; int n;
typedef struct
{
int v;
int yu;
int num;
int pre;
}PP; int tot;
int vis[];
PP ans[N]; void ini()
{
tot=;
memset(vis,,sizeof(vis));
} void out(int now)
{
// for(int i=0;i<=1;i++)
//printf(" v=%d pre=%d\n",ans[i].v,ans[i].pre);
//printf(" now=%d v=%d pre=%d\n",now,ans[now].v,ans[now].pre);
if(ans[now].pre!=-){ out(ans[now].pre); }
printf("%d",ans[now].v);
} void bfs()
{
queue<PP>q;
PP te,nt;
te.v=;
te.pre=-;
te.num=;
te.yu=%n;
ans[].v=;
ans[].pre=-;
tot=;
vis[]=;
q.push(te); while(q.size()>=)
{ te=q.front();
q.pop();
// printf(" v=%d yu=%d num=%d pre=%d\n",te.v,te.yu,te.num,ans[te.num].pre);
if(te.yu==){
//printf(" num=%d\n",te.num);
out(te.num);
printf("\n");
return;
}
nt.pre=te.num;
nt.yu=(te.yu*)%n;
if(vis[nt.yu]==){
vis[nt.yu]=;
nt.num=tot;
ans[tot].v=;
ans[tot].pre=te.num;
tot++; nt.v=;
q.push(nt);
}
nt.yu=(te.yu*+)%n;
if(vis[nt.yu]==){
vis[nt.yu]=;
nt.num=tot;
ans[tot].v=;
ans[tot].pre=te.num;
tot++;
nt.v=;
q.push(nt);
}
}
} void solve()
{
bfs();
} int main()
{
//freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
//scanf("%d",&T);
//for(int ccnt=1;ccnt<=T;ccnt++)
//while(T--)
while(scanf("%d",&n)!=EOF)
{
if(n==) break;
ini();
solve();
// out();
} return ;
}