Cod sursa(job #2953324)

Utilizator gifiVidru Rares gifi Data 10 decembrie 2022 23:39:49
Problema Multiplu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <fstream>
#include <Queue>
using namespace std;
ifstream cin("multiplu.in");
ofstream cout("multiplu.out");
int a,b,auxa,auxb,cmmmc,r,i,r0,r1,prv[2000001];
queue<int>Q;
void reconst(int r)
{if (r==1)
    {cout<<1;
        return;
    }
int rest=prv[r];
reconst(rest);
if ((rest*10)%cmmmc==r) cout<<0;
    else cout<<1;
}
int main()
{cin>>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;
}