Cod sursa(job #2912104)

Utilizator euyoTukanul euyo Data 6 iulie 2022 19:53:07
Problema Multiplu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <bits/stdc++.h>

using namespace std;

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

const int MAXN = 2e6 + 5;

struct str {
  int rem, d, from;
};

vector<str> q;
bool inq[MAXN];

int main() {
  int a, b, idx = 0;

  fin >> a >> b;
  a = a * b / __gcd(a, b);
  q.push_back( {1, -1, -1} );
  while ( idx < (int)q.size() && q[idx].rem )  {
	int t = q[idx].rem;
	if ( !inq[(t * 10) % a] ) {
	  q.push_back( {(t * 10) % a, 0, idx} );
	  inq[(t * 10) % a] = true;
	}
	if ( !inq[(t * 10 + 1) % a] ) {
	  q.push_back( {(t * 10 + 1) % a, 1, idx} );
	  inq[(t * 10 + 1) % a] = true;
	}
    ++idx;
  }
  vector<int> sol;
  while ( q[idx].from != -1 ) {
	sol.push_back( q[idx].d );
	idx = q[idx].from;
  }
  sol.push_back(1);
  reverse(sol.begin(), sol.end());
  for ( auto v : sol ) fout << v;
  fin.close();
  fout.close();
  return 0;
}