Cod sursa(job #2229186)

Utilizator lucametehauDart Monkey lucametehau Data 6 august 2018 10:19:27
Problema Multiplu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

const int NMAX = 2e6;

int n, a, b;
int st, dr, top;

int q[1 + NMAX];
int last1[1 + NMAX];
bool f[1 + NMAX], sol[1 + NMAX];

int main() {
  cin >> a >> b;
  a = a * b / __gcd(a, b);
  st = dr = 1;
  q[1] = 1;
  f[1] = 1;
  for(int i = 0; i < a; i++)
    last1[i] = -1;
  last1[1] = 0;
  while(st <= dr) {
    top = q[st++];
    if(last1[10 * top % a] == -1) {
      q[++dr] = 10 * top % a;
      f[10 * top % a] = 0;
      last1[10 * top % a] = top;
      if(10 * top % a == 0)
        break;
    }
    if(last1[(10 * top + 1) % a] == -1) {
      q[++dr] = (10 * top + 1) % a;
      f[(10 * top + 1) % a] = 1;
      last1[(10 * top + 1) % a] = top;
      if((10 * top + 1) % a == 0)
        break;
    }
  }
  sol[++n] = f[0];
  top = last1[0];
  while(top) {
    sol[++n] = f[top];
    top = last1[top];
  }
  for(int i = n; i >= 1; i--)
    cout << sol[i];
  return 0;
}