Cod sursa(job #176449)

Utilizator juniorOvidiu Rosca junior Data 11 aprilie 2008 11:51:23
Problema Multiplu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<stdio.h>

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

long long cmmdc(long long a,long long 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("%lld %lld",&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;
}