Cod sursa(job #2766695)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 2 august 2021 21:30:28
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("multiplu.in");
ofstream fout("multiplu.out");

const int MAXV = 2e6;
int prv[MAXV];
bitset<MAXV> bit;

void print(int x) {
  if (x == -1)
    return;
  print(prv[x]);
  fout << bit[x];
}

int main() {
  int a, b;
  fin >> a >> b;
  int lcm = a / __gcd(a, b) * b;
  queue<int> q;
  q.emplace(1);
  prv[1] = -1;
  bit[1] = 1;
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    bool ok = true;
    for (int i = 0; i < 2 && ok; ++i) {
      int new_x = (x * 10 + i) % lcm;
      if (prv[new_x] == 0) {
        prv[new_x] = x;
        bit[new_x] = i;
        if (new_x == 0)
          ok = false;
        else q.emplace(new_x);
      }
    }
    if (!ok)
      break;
  }
  print(0);
  fin.close();
  fout.close();
  return 0;
}