Cod sursa(job #2863034)

Utilizator PatruMihaiPatru Mihai PatruMihai Data 6 martie 2022 11:37:28
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("multiplu.in");
ofstream fout("multiplu.out");

int rest[2000007];
int cif[2000007];

void afisare(int r)
{
    if(r != 1)
    {
        afisare(rest[r]);
    }

    fout << cif[r];

}

int main()
{
    int a, b;
    fin >> a >> b;
    int c = a * b / __gcd(a, b);

    queue<int> q;
    rest[1] = 1;
    cif[1] = 1;

    q.push(1);

    while(!q.empty())
    {
        int x = q.front();
        q.pop();

        if(x == 0)
        {
            break;
        }

        for(int u = 0; u < 2; u++)
        {
            int aux = (x * 10 + u) % c;

            if(!rest[aux])
            {
                rest[aux] = x;
                cif[aux] = u;
                q.push(aux);
            }
        }
    }

    afisare(0);

    return 0;
}