Cod sursa(job #3139308)

Utilizator ingrid.mitzuIngrid Nagy ingrid.mitzu Data 27 iunie 2023 10:37:58
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb

#include <fstream>
#include <queue>

using namespace std;

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

const int nmax = 2e6+5;

queue <int> q;
int stop;
bool viz[nmax];
int up[nmax];
int m;

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

void reconst (int r)
{
    if ( r==1 ) fout << "1";
    else 
    {
        reconst (up[r]);
        if ( (up[r]*10)%m == r ) fout << "0";
        else fout << "1";
    }
}
int main()
{
    int a, b;
    fin >> a >> b;
    m=a*b/cmmdc(a,b);
    stop=0;
    if ( m==1 ) fout << "1";
    else
    {
        q.push(1);
        viz[1]=1;
    while (stop==0)
    {
        int rest=q.front ();
        q.pop();
        //primul nr generat 
        int nextr=(rest*10)%m;
        if (!viz[nextr])
        {
            viz[nextr]=1;
            q.push(nextr);
            up[nextr]=rest;
        }
        if (nextr==0) stop=1;
        //al doilea numar generat 
        nextr=(rest*10+1)%m;
        if (!viz[nextr])
        {
            viz[nextr]=1;
            q.push(nextr);
            up[nextr]=rest;
        }
        if (nextr==0) stop=1;
    }
    }
    reconst (0);
    return 0;
}