Cod sursa(job #2786266)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 20 octombrie 2021 16:51:20
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 2e6 + 5;

bool viz[N];
int ant[N];
char val[N];

void bfs(int mod) {
  queue<int> q;
  q.push(1);
  viz[1] = true;
  val[1] = '1';
  ant[1] = -1;
  while (!q.empty()) {
    auto rest = q.front();
    q.pop();
    int cu0 = rest * 10 % mod;
    int cu1 = (rest * 10 + 1) % mod;
    if (!viz[cu0]) {
      viz[cu0] = true;
      ant[cu0] = rest;
      val[cu0] = '0';
      if (!cu0)
        return;
      q.push(cu0);
    }
    if (!viz[cu1]) {
      viz[cu1] = true;
      ant[cu1] = rest;
      val[cu1] = '1';
      if (!cu1)
        return;
      q.push(cu1);
    }
  }
}

int main() {
  ifstream cin("multiplu.in");
  ofstream cout("multiplu.out");
  int a, b, x;
  cin >> a >> b;
  cin.close();
  x = a * b / __gcd(a, b);
  bfs(x);
  int nod = 0;
  string s;
  s.reserve(100);
  while (nod != -1) {
    s.push_back(val[nod]);
    nod = ant[nod];
  }
  reverse(s.begin(), s.end());
  cout << s;
  cout.close();
  return 0;
}