Cod sursa(job #2307186)

Utilizator NOSCOPEPROKENDYMACHEAMACUMVREAU NOSCOPEPROKENDY Data 23 decembrie 2018 22:20:13
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <bits/stdc++.h>

#define DIM 2000005



using namespace std;



ifstream fin  ("multiplu.in");

ofstream fout ("multiplu.out");



int a, b, m, x, k, i, p, nr, cnt, ok;

int cif[DIM], sol[DIM], ant[DIM];



queue <int> q;



bitset <DIM> v;



inline int cmmdc (int a, int b){

    if (a%b == 0){

        return b;

    }

    return cmmdc (b, a%b);

}



int main(){

    fin >> a >> b;

    if (a*b == 1){

        fout << 1;

        return 0;

    }

    m = (a*b)/cmmdc(a, b); /// m = cmmmc (a, b)

    q.push(1); /// in q am cele mai mici numere formate cu 0 si 1 care dau un anumit rest la impartirea cu m (introduc, de fapt, resturile lor la m - in numar de maxim m-1)

    v[1] = 1; /// viz

    cif[1] = 1; /// tip

    ant[1] = -1; /// anterior

    while (!q.empty()){

        k = q.front();

        q.pop();

        for (i=0; i<=1; i++){

            p = (10*k + i);

            while (p >= m){

                p -= m;

            }

            if (!v[p]){

                v[p] = 1;

                ant[p] = k;

                cif[p] = i;

                q.push(p);

            }

        }

    }

    while(ok != -1) {

        sol[++nr] = cif[ok];

        ok = ant[ok];

    }

    for (i=nr; i>=1; i--){

        fout << sol[i];

    }

    return 0;

}