Cod sursa(job #324971)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 18 iunie 2009 13:26:45
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 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;
 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;
}