Cod sursa(job #2866263)

Utilizator AnSeDraAndrei Sebastian Dragulescu AnSeDra Data 9 martie 2022 15:37:37
Problema Multiplu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
const int Nmax=2000000;
int previ[Nmax+5], viz[Nmax+5];
queue<int> q;
int x;
int reconst(int r)
{
    if(r==1)
    {
        fout<<1;
        return 1;
    }
    reconst(previ[r]);
    if((previ[r]*10)%x==r)
    {
        fout<<0;
    }
    else
    {
        fout<<1;
    }
}
int main()
{
    int a,b,r,aa,bb,r0,r1;
    fin>>a>>b;
    aa=a;
    bb=b;
    while(b!=0)
    {
        r=a%b;
        a=b;
        b=r;
    }
    x=aa*bb/a;
    q.push(1);
    while(!q.empty())
    {
        r=q.front();
        q.pop();
        if(!r)
        {
            break;
        }
        r0=(r*10)%x;
        if(!viz[r0])
        {
            viz[r0]=1;
            previ[r0]=r;
            q.push(r0);
        }
        r1=(r*10+1)%x;
        if(!viz[r1])
        {
            viz[r1]=1;
            previ[r1]=r;
            q.push(r1);
        }
    }
    reconst(0);
    return 0;
}