n的倍数
时间限制 : 15000 ms    内存限制 : 32 MB
提交次数 : 96    通过次数 : 31
题目描述
va有时候没带电脑来实验室, 他又太无聊了, dxp又不在, 他就想偷偷用dxp的电脑来盘dota, sanguosha什么的。va打开了电脑,来到登陆界面, dxp居然设置了密码, 不过好在还有密码提示(估计是密码太长了dxp也记不住吧)。密码提示:密码是一个只含0和1的整数，这个数又是给定整数n的倍数， 而且尽可能的小。
输入描述
每行输入一个数n(n<=10000)。
输出描述
输出密码。
样例输入
1
2

样例输出
1
10

http://192.168.7.42/problemDetail.aspx?pid=1414   hehe

#include <iostream>
#include <climits>
#include <queue>
#include <stack>
using namespace std;

const int maxn = 10000 + 5;

struct {
    char val; //last digit 0 or 1, -1 for illegal
    int prev;
} a[maxn];

int Queue[maxn];
int * const Stack = Queue;

int main()
{
    int n;
    while (scanf("%d", &n) != EOF){
        if (n == 0){
            printf("0\n");
            continue;
        }

        //init
        for (int i = 0; i < n; i++){
            a[i].val = -1;
        }
        a[1 % n].val = '1';
        a[1 % n].prev = -1;

        int *Base, *Top;
        Base = Top = Queue;
        *Top++ = 1;
        while (Base != Top && a[0].val == -1){
            int x = *Base++;

            int y = (x * 10) % n;
            if (a[y].val == -1){
                a[y].val = '0';
                a[y].prev = x;
                *Top++ = y;
            }

            int z = y + 1;
            if (z >= n) z -= n;
            if (a[z].val == -1){
                a[z].val = '1';
                a[z].prev = x;
                *Top++ = z;
            }
        }

        Base = Top = Stack;
        int x = 0;
        do {
            *Top++ = a[x].val;
            x = a[x].prev;
        } while (x != -1);

        while (Base != Top){
            putchar(*--Top);
        }
        putchar('\n');
    }
return 0;
}

 这代码能AC  供大家参考