Cod sursa(job #218869)

Utilizator alex23alexandru andronache alex23 Data 3 noiembrie 2008 21:04:35
Problema Multiplu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <stdio.h>
#define NMAX 2000100


FILE *f = fopen("multiplu.in", "r"), *g = fopen("multiplu.out", "w");
int up[NMAX], cif[NMAX], st[NMAX], sol[100];
char v[NMAX];
int k;
int a, b, m, prod, lung;
int x;

int main()
  {
   fscanf(f, "%d %d", &a, &b);
   fclose(f);

   if (a < b) {int x = a; a = b; b = x;}
   prod = a * b;

   while (b)
     {
         x = b;
         b = a % b;
         a = x;
     }
  int d = a;

  m = prod / d;
  for (int i = 1; i <= m; i++)
      v[i] = 0;
  v[1] = 1;

  st[1] = 1;
  cif[1] = 1;
  k = lung = 1;

  while (st[k])
     {
      if (v[(st[k] * 10) % m] == 0)
                {st[++lung] = (st[k] * 10) % m;
                 up[lung] = k;
                 cif[lung] = 0;
                 v[st[lung]] = 1;
                }
      if (v[(st[k] * 10 + 1) % m] == 0)
                {
                 st[++lung] = (st[k] * 10 + 1) % m;
                 up[lung] = k;
                 cif[lung] = 1;
                 v[st[lung]] = 1;
                }
     k++;
     }   
  
  int i = 0;
  while (k > 0)
     {i++;
      sol[i] = cif[k];
      k = up[k];
     }
  
  for (int j = 1; j <= i; j++)
     fprintf(g, "%d", sol[j]);
  fclose(g);
  return 0;
  }