Mai intai trebuie sa te autentifici.

Cod sursa(job #2149595)

Utilizator ApostolIlieDanielApostol Daniel ApostolIlieDaniel Data 2 martie 2018 19:21:00
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e6;

int l[MAXN + 1], t[MAXN + 1], v[MAXN + 1], hz[MAXN + 1];

char rez[MAXN + 1];

int main() {
  FILE *fin, *fout;
  int a, b, r, mod, st, dr, i, k, alfa, ok, n;
  fin = fopen ("multiplu.in", "r");
  fout = fopen ("multiplu.out", "w");
  fscanf (fin, "%d%d", &a, &b);
  mod = a * b;
  while (b > 0) {
    r = a % b;
    a = b;
    b = r;
  }
  mod = mod / a;
  v[1] = 1;
  l[1] = 1;
  t[1] = -1;
  hz[1] = 1;
  n = ok = 0;
  st = 1;
  dr = 1;
  while (st <= dr) {
    for (i = 0; i <= 1; i++) {
      k = (v[st] * 10 + i) % mod;
      if (hz[k] == 0) {
        dr++;
        v[dr] = k;
        t[dr] = st;
        l[dr] = i;
        hz[k] = 1 ;
        if (v[dr] == 0) {
          alfa = dr;
          ok = 1;
          break;
        }
      }
    }
    if (ok == 1) {
      break;
    }
    st++;
  }
  while (alfa != -1) {
    n++;
    rez[n] = l[alfa] + 48;
    alfa = t[alfa];
  }
  for (i = 1; i <= n / 2; i++) {
    swap (rez[i], rez[n - i + 1]);
  }
  for (i = 1; i <= n; i++)
    fprintf (fout, "%c", rez[i]);
  fclose (fin);
  fclose (fout);
  return 0;
}