Cod sursa(job #258219)

Utilizator ConsstantinTabacu Raul Consstantin Data 14 februarie 2009 21:05:42
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include<stdio.h>
#include<string.h>
#define n_max 2000100
int v[n_max],ant[n_max],nr[n_max],i,x,j,k,l,m,n,a,b,p,q;

void afis(int q){
if(ant[q]!=-1)
        afis(ant[q]);
printf("%d",nr[q]);
}

int main(){
 freopen("multiplu.in","r",stdin);  
    freopen("multiplu.out","w",stdout);  
scanf("%d %d",&a,&b);
n=a;m=b;
while(b)
{k=a%b;
a=b;b=k;
}
k=(n*m)/a;
p=q=1;
v[1]=1;
ant[1]=-1;
memset(nr,-1,sizeof(nr));
nr[1]=1;
//fill();
  while(p<=q)
        {x=(v[p]*10)%k;
        if(nr[x]==-1)
                {v[++q]=x;
                ant[x]=v[p];
                nr[x]=0;
                if(!x){
                afis(0);return 0;}}
       x=(v[p]*10+1)%k;
      if(nr[x]==-1)
                {v[++q]=x;
                ant[x]=v[p];
                nr[x]=1;
                if(!x){afis(0);
                return 0;}
                }
     p++;}

return 0;}