Cod sursa(job #2942235)

Utilizator Luca_CristianZamfir Luca-Cristian Luca_Cristian Data 19 noiembrie 2022 13:37:42
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <queue>
#include <fstream>

using namespace std;

ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
#define int long long
const int Nmax = 2000001;
int last[Nmax], fact;
bool viz[Nmax];
queue <int> q;

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

void getans(int r)
{
    if(r == 1)
    {
        fout << 1;
        return;
    }
    else
    {
        getans(last[r]);
        if((last[r] * 10) % fact == r)
            fout << 0;
        else
            fout << 1;
    }
}


signed main()
{
    int a, b;

    fin >> a >> b;

    fact = (a * b) / euclid(a, b);

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

        if(ur == 0)
            break;

        r = (ur * 10) % fact;
        if(!viz[r])
        {
            q.push(r);
            last[r] = ur;
            viz[r] = 1;
        }
        r = (ur * 10 + 1) % fact;
        if(!viz[r])
        {
            q.push(r);
            last[r] = ur;
            viz[r] = 1;
        }
        ///fout << ur * 10 << " " << ur * 10 + 1 << "  " << (ur * 10) % fact << " " << (ur * 10 + 1) % fact << endl;
    }
    getans(0);



    return 0;
}