Cod sursa(job #2920882)

Utilizator ANDRAGABRIELACirstoiu Andra-Gabriela ANDRAGABRIELA Data 26 august 2022 14:38:49
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>
#include <queue>

using namespace std;
ifstream f("multiplu.in");
ofstream g("multiplu.out");
int a,b,auxa,auxb,cmmmc,r,i,r0,r1,prv[2000001];
queue<int>q;
void reconst(int r)
{
    if(r==1)
    {
        g<<1;
        return;
    }
    int rest=prv[r];
    reconst(rest);
    if((rest*10)%cmmmc==r)g<<0;
    else g<<1;
}
int main()
{
    f>>a>>b;
    auxa=a;
    auxb=b;
    while(b!=0)
    {
        r=a%b;
        a=b;
        b=r;
    }
    cmmmc=(auxa*auxb)/a;
    for(i=0;i<cmmmc;i++)prv[i]=-1;
    prv[1]=1;
    q.push(1);
    while(!q.empty())
    {
        r=q.front();
        q.pop();
        if(r==0)break;
        r0=(r*10)%cmmmc;
        if(prv[r0]==-1)
        {
            prv[r0]=r;
            q.push(r0);
        }
        r1=(r*10+1)%cmmmc;
        if(prv[r1]==-1)
        {
            prv[r1]=r;
            q.push(r1);
        }
    }
    reconst(0);
    return 0;
}