Cod sursa(job #1802700)

Utilizator ionutpop118Pop Ioan Cristian ionutpop118 Data 10 noiembrie 2016 16:30:36
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <cstdio>
#include <queue>
using namespace std;
const int NMAX = 2000000;

queue <int> q; int sol[NMAX + 5];
int viz[NMAX + 5];
int last[NMAX + 5];
int cif[NMAX + 5];

int cmmdc(int a, int b)
{
    int r;
    while (b != 0)
    {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}
int main()
{
    freopen("multiplu.in", "r", stdin);
    freopen("multiplu.out", "w", stdout);
    int a, b, ans, aux, nou;

    scanf("%d %d", &a, &b);
    ans = a * b / cmmdc(a, b);
    if (ans <= 1)
    {
        printf("%d\n", ans);
        return 0;
    }
    q.push(1); viz[1] = 1;
    last[1] = -1; cif[1] = 1;
    while (!q.empty())
    {
        aux = q.front();
        if (aux == 0)
            break;
        /// adaugam 0 ///
        nou = (aux * 10 + 0) % ans;
        if (viz[nou] == 0)
        {
            viz[nou] = 1;
            last[nou] = aux;
            cif[nou] = 0;
            q.push(nou);
        }
        /// adaugam 1 ///
        nou = (aux * 10 + 1) % ans;
        if (viz[nou] == 0)
        {
            viz[nou] = 1;
            last[nou] = aux;
            cif[nou] = 1;
            q.push(nou);
        }
        q.pop();
    }

    int nr = 0;
    while (aux != -1)
    {
        sol[++nr] = cif[aux];
        aux = last[aux];

    }
    for (; nr > 0; --nr)
        printf("%d", sol[nr]);
    return 0;
}