ONEZERO.cpp

#include <iostream>
using namespace std;
 
const int MAX = 20005;
 
int  N, Exist[MAX], Parent[MAX];
int  current, expanding, remainder, len;
char Digit[MAX], Temp[MAX];
 
int queue[MAX];
int fr, re, leng;
 
void Enqueue(int remainder)
{
    queue[re] = remainder;
    re = (re + 1) % MAX;
    leng++;
}
 
int Dequeue()
{
    int c = queue[fr];
    fr = (fr + 1) % MAX;
    leng--;
    return c;
}
 
int main()
{
    ios::sync_with_stdio(false);
 
    // Comment trước khi submit
    freopen("input.txt","r",stdin);
 
    int K;
    cin >> K;
 
    for(int i = 0; i < K; i++)
    {
        cin >> N;
 
        for(int i = 0; i < N; i++)
        {
            Exist[i] = 0;
            Parent[i]= 0;
            Digit[i] = '0';
            Temp[i]  = '0';
        }
 
        // Nếu đầu vào là 1 => số cần tìm cũng là 1
        if(N == 1)
        {
            cout << 1 << endl;
            continue;
        }
        
        // Duyệt tất cả các trạng thái
        Parent[1] = -1;
        Digit[1]  = '1';
        Exist[1]  = 1;
 
        Enqueue(1);
 
        while(leng > 0)
        {
            current = Dequeue();
 
            for(int i = 0; i < 2; i++)
            {
                // xét trạng thái kề với current
                expanding = current * 10 + i;
                remainder = expanding % N;
 
                if(Exist[remainder] == 0)
                {
                    Exist[remainder]  = 1;
                    Parent[remainder] = current;
                    Digit[remainder]  = i + '0';
                    
                    Enqueue(remainder);
                }
            }
        }
 
        // Truy lại số cần tìm
        current = 0;
        len    = 0;
 
        while(true)
        {
            Temp[len++] = Digit[current];
 
            if(Parent[current] == -1) break;
            else current = Parent[current];
        }
 
        for(int i = len - 1; i >= 0; i--)
            cout << Temp[i];
        cout << endl;
    }
 
    return 0;
}