#1181209 (C++23(gcc16)) No.3663 LCM Decomposition

• 問題: No.3663 LCM Decomposition
• ユーザー: ei1333333
• 提出日時: 2026-08-30 15:08:21
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0)
• 結果: AC
• 実行時間: 51 ms / 1,000 ms
• コード長: 3,650 bytes
• コンパイル時間: 5,462 ms
• コンパイル使用メモリ: 399,088 KB
• 実行使用メモリ: 6,272 KB
• 最終ジャッジ日時: 2026-08-30 15:08:28
• 合計ジャッジ時間: 7,118 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
sample	AC * 1
other	AC * 14

ソースコード

#line 1 "template/template.hpp"
#include <bits/stdc++.h>

#if __has_include(<atcoder/all>)
#include <atcoder/all>

#endif

using namespace std;

using int64 = long long;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;

template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
  os << p.first << " " << p.second;
  return os;
}

template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
  is >> p.first >> p.second;
  return is;
}

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  for (size_t i = 0; i < v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& in : v) is >> in;
  return is;
}

template <typename T1, typename T2>
bool chmax(T1& a, T2 b) {
  return a < b && (a = b, true);
}

template <typename T1, typename T2>
bool chmin(T1& a, T2 b) {
  return a > b && (a = b, true);
}

template <typename T = int64>
vector<T> make_v(size_t a) {
  return vector<T>(a);
}

template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
  return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

template <typename T, typename V>
enable_if_t<is_class_v<T> == 0> fill_v(T& t, const V& v) {
  t = v;
}

template <typename T, typename V>
enable_if_t<is_class_v<T> != 0> fill_v(T& t, const V& v) {
  for (auto& e : t) fill_v(e, v);
}

template <typename F>
struct FixPoint : F {
  explicit FixPoint(F&& f) : F(std::forward<F>(f)) {}

  template <typename... Args>
  decltype(auto) operator()(Args&&... args) const {
    return F::operator()(*this, std::forward<Args>(args)...);
  }
};

template <typename F>
decltype(auto) MFP(F&& f) {
  return FixPoint<F>{std::forward<F>(f)};
}
#line 2 "math/number-theory/prime-factor.hpp"

#include <cstdint>
#include <map>

std::map<std::int64_t, int> prime_factor(std::int64_t n) {
  std::map<std::int64_t, int> ret;
  for (std::int64_t i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if (n != 1) ret[n] = 1;
  return ret;
}

void sub() {
  int N, L, R;
  cin >> N >> L >> R;
  vector< pair< int, int > > pf;
  {
    auto buf = prime_factor(N);
    pf = {buf.begin(), buf.end()};
  }

  vector< vector< int > > cand(1 << pf.size());
  auto dfs = MFP([&](auto dfs, int idx, int v, int mask) -> void {
    if (idx == pf.size()) {
      if (L <= v and v <= R and cand[mask].size() < 3) {
        cand[mask].emplace_back(v);
      }
      return;
    }
    for (int i = 0; i <= pf[idx].second; i++) {
      if (i == pf[idx].second) {
        dfs(idx + 1, v, mask | (1 << idx));
      }
      dfs(idx + 1, v, mask);
      v *= pf[idx].first;
    }
  });
  dfs(0, 1, 0);
  int mask = (1 << pf.size()) - 1;
  for (int i = mask;; i = i - 1 & mask) {
    int zan = mask ^ i;
    for (int j = zan;; j = j - 1 & zan) {
      int k = mask^i^j;
      for (auto& a : cand[i]) {
        for (auto& b : cand[j]) {
          if (a != b) {
            for (auto& c : cand[k]) {
              if (a != c and b != c) {
                vector ans{a, b, c};
                ranges::sort(ans);
                cout << ans << endl;
                return;
              }
            }
          }
        }
      }
      if (j == 0) break;
    }
    if (i == 0) break;
  }
  cout << -1 << "\n";
}

int main() {
  int T;
  cin >> T;
  while (T--) {
    sub();
  }
}