Cod sursa(job #2866265)

Utilizator AnSeDraAndrei Sebastian Dragulescu AnSeDra Data 9 martie 2022 15:42:20
Problema Multiplu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
const int Nmax=100000;
int previ[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(previ[r0]==0)
        {
            previ[r0]=r;
            q.push(r0);
        }
        r1=(r*10+1)%x;
        if(previ[r1]==0)
        {
            previ[r1]=r;
            q.push(r1);
        }
    }
    reconst(0);
    return 0;
}