Cod sursa(job #130976)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 2 februarie 2008 19:03:19
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include<stdio.h>
FILE*fin=fopen("multiplu.in","r");
FILE*fout=fopen("multiplu.out","w");
int a,b,crest[2000001],wf[2000001],aux,p,m;
char us[2000001],uc[2000001];
void rec(int poz)
{
  if(poz==0) fprintf(fout,"%d",1);
  else{rec(wf[poz]);fprintf(fout,"%d",uc[poz]);}
}
int main()
{
  int dr,st,i;
  fscanf(fin,"%d%d",&a,&b);
  fclose(fin);
  p=a*b;
  if(a<b) a^=b^=a^=b;
  while(b!=0)
  {
    aux=a;
    a=b;
    b=aux%b;
  }
  m=p/a;
  for(i=0;i<m;i++)
    us[i]=0;
  us[1]=1;
  st=dr=0;
  crest[0]=1;wf[0]=-1;uc[0]=1;
  while(st<=dr)
  {
    if(us[(crest[st]*10)%m]==0)
    {
      dr++;
      crest[dr]=(crest[st]*10)%m;
      us[crest[dr]]=1;
      uc[dr]=0;
      wf[dr]=st;
      if(crest[dr]==0) break;
    }
    if(us[(crest[st]*10+1)%m]==0)
    {
      dr++;
      crest[dr]=(crest[st]*10+1)%m;
      us[crest[dr]]=1;
      uc[dr]=1;
      wf[dr]=st;
      if(crest[dr]==0) break;
    }
    st++;
  }
  rec(dr);
  fclose(fout);
  return 0;
}