Cod sursa(job #2785834)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 19 octombrie 2021 17:09:40
Problema Multiplu Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 2e6 + 5;

bool viz[N];
int ant[N], p10[N];
vector<int> v, tmp;

int main() {
  ifstream cin("multiplu.in");
  ofstream cout("multiplu.out");
  int a, b, x;
  cin >> a >> b;
  x = a * b / __gcd(a, b);
  p10[0] = viz[1] = 1;
  v.push_back(1);
  for (int i = 1; i <= N; ++i) {
    p10[i] = (long long) p10[i - 1] * 10 % x;
    tmp.clear();
    for (auto j : v) {
      int nou = (j + p10[i]) % x;
      if (!viz[nou]) {
        viz[nou] = true;
        tmp.push_back(nou);
        ant[nou] = i;
      }
    }
    for (auto j : tmp)
      v.push_back(j);
    if (!viz[p10[i]]) {
      viz[p10[i]] = true;
      v.push_back(p10[i]);
      ant[p10[i]] = i;
    }
    if (viz[0]) break;
  }
  int p = ant[0], s = 0;
  string ans;
  ans.reserve(1000);
  while (true) {
    ans.push_back('1');
    s -= p10[p];
    if (s < 0) s += x;
    if (!s)
      break;
    int urm = ant[s];
    for (int i = 0; i < p - urm - 1; ++i)
      ans.push_back('0');
    p = urm;
  }
  while (p > 0)
    ans.push_back('0'), --p;
  cout << ans;
  cin.close();
  cout.close();
  return 0;
}