Cod sursa(job #1606689)

Utilizator andy1207Cioltan Andrei andy1207 Data 20 februarie 2016 14:23:17
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<cstdio>
int ucif[2000001];
int anterior[2000001];
int q[2000001];
void refacere(int x)
{
 if(anterior[x]!=0)
    refacere(anterior[x]);
 printf("%d",ucif[x]);
}
int main()
{
 int a,b,ca,cb,m,r,x,y,i,p,u;
 freopen("multiplu.in","r",stdin);
 freopen("multiplu.out","w",stdout);
 scanf("%d%d",&a,&b);
 ca=a;
 cb=b;
 while(b!=0)
      {
       r=a%b;
       a=b;
       b=r;
      }
 m=(ca*cb)/a;
 for(i=0;i<=m;i++)
    {
     ucif[i]=anterior[i]=-1;
    }
 p=u=0;
 q[u++]=1;
 ucif[1]=1;
 anterior[1]=0;
 while(p!=u)
      {
       x=q[p++];
       for(i=0;i<=1;i++)
          {
           y=(x*10+i)%m;
           if(ucif[y]==-1)
              {
               q[u++]=y;
               ucif[y]=i;
               anterior[y]=x;
              }
          }
      }
 refacere(0);
 printf("\n");
return 0;
}