Cod sursa(job #1006052)

Utilizator poptibiPop Tiberiu poptibi Data 6 octombrie 2013 10:57:02
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;

const int NMAX = 2000010;

int Queue[NMAX], Prev[NMAX], D[NMAX], A, B, Front, Back, M;
bool Used[NMAX];

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

int LCM(int A, int B)
{
    return (A * B) / GCD(A, B);
}

void Reconstr(int Pos)
{
    if(Pos == -1) return ;
    Reconstr(Prev[Pos]);
    printf("%i", D[Pos]);
}

int main()
{
    freopen("multiplu.in", "r", stdin);
    freopen("multiplu.out", "w", stdout);

    scanf("%i %i", &A, &B);
    M = LCM(A, B);

    Queue[Front = Back = 1] = 1;
    Prev[1] = -1;
    D[1] = 1;
    Used[1] = 1;

    while(Back <= M)
    {
        int Rest = Queue[Front];
        if(Rest == 0)
        {
            Reconstr(Front);
            return 0;
        }
        if(!Used[(Rest * 10) % M])
        {
            Queue[++Back] = (Rest * 10) % M;
            Used[(Rest * 10) % M] = 1;
            Prev[Back] = Front;
            D[Back] = 0;
        }
        if(!Used[(Rest * 10 + 1) % M])
        {
            Queue[++Back] = (Rest * 10 + 1) % M;
            Used[(Rest * 10 + 1) % M] = 1;
            Prev[Back] = Front;
            D[Back] = 1;
        }

        Front ++;
    }

    return 0;
}