Codeforces/1829/d.cpp

#include <algorithm>
#include <cassert>
#include <cctype>
#include <cstdint>
#include <functional>
#include <iostream>
#include <optional>
#include <sstream>
#include <string>
#include <vector>

namespace helpers {

using namespace std;

long pow(long base, long exp) {
  if (exp == 0) return 1;
  long half = pow(base, exp / 2);
  if (exp % 2 == 0) return half * half;
  return half * half * base;
}

template <typename T>
inline void answer(const T &ans) {
  cout << ans << "\n";
}

inline void yes() { cout << "YES\n"; }
inline void no() { cout << "NO\n"; }

inline void yesno(bool ans) {
  if (ans) {
    yes();
  } else {
    no();
  }
}

}  // namespace helpers

namespace {

using namespace std;
using namespace helpers;

bool can_split(int n, int m) {
  if (n == m) {
    // we already have a pile
    return true;
  }

  if (n < m) {
    // cannot make bigger pile
    return false;
  }

  if (n % 3 != 0) {
    // cannot split the pile
    return false;
  }

  int third = n / 3;
  return can_split(third, m) || can_split(2 * third, m);
}

void solve() {
  int n, m;
  cin >> n >> m;
  yesno(can_split(n, m));
}

}  // namespace

// for single test case, comment out for ‹N› test cases
// #define SINGLE

#ifdef TEST

#include "../.common/cpp/catch_amalgamated.hpp"

TEST_CASE("examples") {
  CHECK(can_split(6, 4));
  CHECK(can_split(9, 4));
  CHECK(!can_split(4, 2));
  CHECK(!can_split(18, 27));
  CHECK(can_split(27, 4));
  CHECK(can_split(27, 2));
  CHECK(!can_split(27, 10));
  CHECK(can_split(1, 1));
  CHECK(can_split(3, 1));
  CHECK(!can_split(5, 1));
  CHECK(!can_split(746001, 2984004));
}

#else

int main(void) {

#ifdef SINGLE

  solve();

#else

  // for multiple test cases
  int N;
  std::cin >> N >> std::ws;

  for (auto i = 0; i < N; ++i) {
    solve();
  }

#endif

  return 0;
}

#endif