POJ 1426 见证模余的力量！

2019-04-14 21:49发布

站内文章 / 模拟电子
11014 0 1478
核心思想：       同余的数只保留一个就足够了。   /*
source: POJ t1426
algorithm: BFS
author: wangmeng @ flame
date: 2009-8-16
*/

#include
#include
using namespace std;

int main()
{
    int n;
    int front;
    int next1;
    int next2;
    bool inQueue[200];
    long long sequence[200] = {0};
    queue q;
    while ((cin >> n) && (n != 0))
    {
        // initialize data
        memset(sequence, 0, sizeof(sequence));
        memset(inQueue, false, sizeof(inQueue));
        sequence[1] = 1;
        inQueue[1] = true;
        while (!q.empty())
            q.pop();
        q.push(1);
        // creat graph
       
        while (!inQueue[0])
        {
            front = q.front();
            q.pop();
            next1 = (front * 10) % n;
            next2 = (next1 + 1) % n;
            if (!inQueue[next1])
            {
                q.push(next1);
                inQueue[next1]  = true;
                sequence[next1] = sequence[front] * 10;
            }
            if (!inQueue[next2])
            {
                q.push(next2);
                inQueue[next2] = true;
                sequence[next2] = sequence[front] *10 + 1;
            }
        }
        cout << sequence[0]<     }
    return 0;
}

热门文章