Cod sursa(job #2285975)

Utilizator MaxTeoTeo Oprescu MaxTeo Data 19 noiembrie 2018 17:23:26
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <bits/stdc++.h>
#define NMAX 2000005
using namespace std;

ifstream f("multiplu.in");
ofstream g("multiplu.out");

int coada[NMAX], cifra[NMAX], drum[NMAX], v[NMAX];
int a, b, M;

void Path(int x)
{
    if(x)
    {
        Path(drum[x]);
        g << cifra[x];
    }
}

int cmmdc(int a, int b)
{
    int r;
    while(b)
    {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main()
{
    int p, u;
    f >> a >> b;

    M = (a * b) / cmmdc(a, b);

    coada[1] = 1;
    v[1] = 1;
    cifra[1] = 1;
    p = u = 1;

    while(p <= u)
    {
        for(int ucif = 0; ucif <= 1; ++ucif)
        {
            int numar = (coada[p] * 10 + ucif) % M;
            if(v[numar] == 0)
            {
                ++u;
                coada[u] = numar;
                cifra[u] = ucif;
                v[numar] = 1;
                drum[u] = p;
                if(numar == 0)
                {
                    p = u + 1;
                    break;
                }
            }
        }
        ++p;
    }

    Path(u);
    return 0;
}