Cod sursa(job #2429279)

Utilizator AlexPop28Pop Alex-Nicolae AlexPop28 Data 8 iunie 2019 19:54:58
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
// Datorez puntajul de la aceasta problema lui Bogdan Pop care mi-a spus solutia
// incercand sa-mi explice alta problema de fapt
// Ma bucur ca pe infoarena problemele de acum un secol nu-si permit vectori
// alocati dinamic numa array uri...
#include <bits/stdc++.h>
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'

using namespace std;

const int NMAX = 2e6;

int dad[NMAX], digit[NMAX];

int main() {
  freopen("multiplu.in", "r", stdin);
  freopen("multiplu.out", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0);

  int a, b;
  cin >> a >> b;
  int lcm = a * b / __gcd(a, b);
  digit[1] = 1;
  dad[1] = -1;
  queue<int> q;
  q.push(1);
  while (!q.empty()) {
    int node = q.front();
    q.pop();
    if (node == 0) {
      break;
    }
    for (int dig = 0; dig < 2; ++dig) {
      int to = (node * 10 + dig) % lcm;
      if (dad[to] == 0) {
        q.push(to);
        dad[to] = node;
        digit[to] = dig;
        if (to == 0) {
          break;
        }
      }
    }
  }
  
  int node = 0;
  vector<int> ans;
  do {
    ans.emplace_back(digit[node]);
    node = dad[node];
  } while (node != -1);
  
  for (int i = (int)ans.size() - 1; i >= 0; --i) {
    cout << ans[i];
  }
  cout << endl;

#ifdef LOCAL_DEFINE
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}