Cod sursa(job #2871248)

Utilizator Luca_CristianZamfir Luca-Cristian Luca_Cristian Data 13 martie 2022 21:09:16
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

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

#define MAXN 2000001
int viz[MAXN], prevv[MAXN];

int gcd(int a, int b)
{
    int r;
    while(b > 0)
    {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}
int x;

void reconst(int r)
{
    if(r == 1)
    {
        fout << 1;
        return;
    }
    reconst(prevv[r]);
    if((prevv[r] * 10) % x == r)
        fout << 0;
    else
        fout << 1;

}




int main()
{
    int a, b;

    fin >> a >> b;

    queue <int> q;

    int r0, r1, r;
    x = (a * b) / gcd(a, b);

    q.push(1);
    while(!q.empty())
    {
        r = q.front();
        q.pop();

        if(r == 0)
            break;

        r0 = (r * 10) % x;
        if(!viz[r0])
        {
            prevv[r0] = r;
            viz[r0]++;
            q.push(r0);
        }
        r1 = (r * 10 + 1) % x;
        if(!viz[r1])
        {
            prevv[r1] = r;
            viz[r1]++;
            q.push(r1);
        }
    }
    reconst(0);




    return 0;
}