Cod sursa(job #1101434)
Utilizator | Data | 8 februarie 2014 14:48:28 | |
---|---|---|---|
Problema | Multiplu | Scor | 30 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.81 kb |
#include<stdio.h>
#include<queue>
struct multiplu
{
int x,bin;
};
int a,b,num,ca,cb,sol,r,tata,i,aux,rest;
int recon[2000001];
multiplu viz[2000001];
using namespace std;
int main()
{
freopen("multiplu.in","r",stdin);
freopen("multiplu.out","w",stdout);
queue<int>q;
scanf("%d%d",&a,&b);
ca=a;
cb=b;
while(b!=0)
{
r=a%b;
a=b;
b=r;
}
sol=ca*cb/a;
aux=1%sol;
viz[aux].bin=1;
q.push(aux);
while(q.empty()==0)
{
tata=q.front();
rest=(tata*10)%sol;
if(rest==0)
{
aux=0;
recon[++num]=0;
while(viz[tata].x!=0)
{
recon[++num]=viz[tata].bin;
tata=viz[tata].x;
}
printf("1");
for(i=num;i>=1;--i)
printf("%d",recon[i]);
printf("\n");
return 0;
}
else
{
q.push(rest);
if(viz[rest].x==0)
{
viz[rest].x=tata;
viz[rest].bin=0;
}
}
rest=(tata*10+1)%sol;
if(rest==0)
{
aux=0;
recon[++num]=1;
while(viz[tata].x!=0)
{
recon[++num]=viz[tata].bin;
tata=viz[tata].x;
}
printf("1");
for(i=num;i>=1;--i)
printf("%d",recon[i]);
printf("\n");
return 0;
}
else
{
q.push(rest);
if(viz[rest].x==0)
{
viz[rest].x=tata;
viz[rest].bin=1;
}
}
q.pop();
}
return 0;
}