Cod sursa(job #2146793)

Utilizator lucametehauDart Monkey lucametehau Data 28 februarie 2018 10:55:13
Problema Multiplu Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>
#include <queue>

using namespace std;

ifstream cin ("multiplu.in");
ofstream cout ("multiplu.out");

const int MAX_N = 2000001;

int a, b, c;
int r, top, nr;
int m;

int last[MAX_N], lastr[MAX_N];
int v[MAX_N];
queue <int> Q;

int main() {
  cin >> a >> b;
  c = a;
  a *= b;
  while(b > 0) {
    r = c % b;
    c = b;
    b = r;
  }
  a /= c;
  Q.push(1);
  last[1] = 1;
  while(!Q.empty()) {
    top = Q.front();
    Q.pop();

    if(lastr[top * 10 % a] == 0) {
      nr = top * 10 % a;
      Q.push(nr);
      last[nr] = 0;
      lastr[nr] = top;
      if(nr == 0)
        break;
    }
    if(lastr[(top * 10 + 1) % a] == 0) {
      nr = (top * 10 + 1) % a;
      Q.push(nr);
      last[nr] = 1;
      lastr[nr] = top;
      if(nr == 0)
        break;
    }
  }
  v[++m] = last[0];
  top = lastr[0];
  while(top) {
    v[++m] = last[top];
    top = lastr[top];
  }
  for(int i = m; i >= 1; i--)
    cout << v[i];
  return 0;
}