Cod sursa(job #129429)

Utilizator marinMari n marin Data 29 ianuarie 2008 14:57:21
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <stdio.h>
#define DIM 2000001
long int c[DIM];
long int t[DIM];
char uc[DIM];
char viz[DIM];
long int p,u,m,r,a,b;
FILE *g;

void sol(long int u){
  if (u!=0) {
    sol(t[u]);
    fprintf(g,"%d",uc[u]);
  }
}

int main(){
  FILE *f = fopen("multiplu.in","r");
  g = fopen("multiplu.out","w");
  fscanf(f,"%ld %ld",&a,&b);
  fclose(f);
  p = a*b;
  while (b!=0) {
    r = a % b;
    a=b;
    b=r;
  }
  m=p/a;
  p=1;
  u=1;
  c[1]=1;
  uc[1]=1;
  t[1]=0;
  viz[1]=1;
  while (p<=u) {
    if (viz[(c[p]*10)%m]==0) {
      u++;
      c[u]=(c[p]*10)%m;
      uc[u]=0;
      viz[(c[p]*10)%m]=1;
      t[u]=p;
      if ((c[p]*10)%m==0){
	sol(u);
	break;
      }
    }

    if (viz[(c[p]*10+1)%m]==0) {
      u++;
      c[u]=(c[p]*10+1)%m;
      uc[u]=1;
      viz[(c[p]*10+1)%m]=1;
      t[u]=p;
      if ((c[p]*10+1)%m==0){
	sol(u);
	break;
      }

    }
    p++;
  }
  fclose(g);
  return 0;
}