Cod sursa(job #176511)

Utilizator juniorOvidiu Rosca junior Data 11 aprilie 2008 12:55:14
Problema Multiplu Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<stdio.h>

int rest[2000001], que[2000001],n,m,val,cap,coada,s[2000001];
char cif[2000001],pt[2000001];
int pt0;
int val1,val2,k,i;

int cmmdc(int a,int b) {
  if (b==0)
    return a;
  cmmdc(b,a%b);
  //return 0;
}

int main() {
  freopen("multiplu.in","r",stdin);
  freopen("multiplu.out","w",stdout);
  scanf("%d %d",&n,&m);
  val=cmmdc(n,m);
  val=(n*m)/val;
  for (i=0;i<=2000000;i++)
    rest[i]=0;
  rest[1]=1;
  que[1]=1;
  cap=1;
  coada=1;
  while (1) {
    val1=(que[cap]*10)%val;
    val2=(que[cap]*10+1)%val;
    if (rest[val1]==0) {
      coada++;
      s[coada]=cap;
      cif[coada]=0;
      que[coada]=val1;
      rest[val1]=1;
    }
    if (rest[0]==1)
      break;
    if (rest[val2]==0) {
      coada++;
      s[coada]=cap;
      cif[coada]=1;
      que[coada]=val2;
      rest[val2]=1;
    }
    if (rest[0]==1)
      break;
    cap++;
  }
  k=coada;
  while (k!=1) {
    pt[pt0++]=cif[k];
    k=s[k];
  }
  pt[pt0++]=1;
  for (i=pt0-1;i>=0;i--)
    printf("%d",pt[i]);
  return 0;
}