Cod sursa(job #254003)

Utilizator Mishu91Andrei Misarca Mishu91 Data 6 februarie 2009 15:00:21
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <cstdio>
#include <queue>
#include <string>

using namespace std;

#define MAX_N 2000005

int A, B, M;
int Ant[MAX_N];
string S;

int gcd(int A, int B)
{
    if(!B) return A;
    return gcd(B, A%B);
}

void search()
{
    queue <int> Q;
    Q.push(1);
    int rest;

    while(!Q.empty())
    {
        int act = Q.front();
        Q.pop();
        rest = (act * 10) % M;
        if(Ant[rest] == 0)
        {
            Q.push(rest);
            Ant[rest] = act;
        }
        if(rest == 0) return;

        rest = (act * 10 + 1) % M;
        if(Ant[rest] == 0)
        {
            Q.push(rest);
            Ant[rest] = act;
        }
        if(rest == 0) return;
    }
}

int main()
{
    freopen("multiplu.in","rt",stdin);
    freopen("multiplu.out","wt",stdout);

    scanf("%d %d",&A, &B);

    M = B / gcd(A, B) * A;
    search();

    int act = 0;
    while(act != 1)
    {
        if((Ant[act] * 10) % M == act) S += '0';
        else S += '1';
        act = Ant[act];
    }
    S += '1';
    reverse(S.begin(), S.end());
    printf("%s\n",S.c_str());
}