#1181258 (C++23) No.3663 LCM Decomposition

• 問題: No.3663 LCM Decomposition
• ユーザー: Nzt3
• 提出日時: 2026-08-30 15:17:05
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0)
• 結果: AC
• 実行時間: 326 ms / 1,000 ms
• コード長: 4,430 bytes
• コンパイル時間: 2,636 ms
• コンパイル使用メモリ: 354,184 KB
• 実行使用メモリ: 6,272 KB
• 最終ジャッジ日時: 2026-08-30 15:18:00
• 合計ジャッジ時間: 5,361 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

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

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
#define rep3(i, a, b, c) for (ll i = (a); i < (b); i += (c))
#define rep2(i, a, b) rep3(i, a, b, 1)
#define rep1(i, n) rep2(i, 0, n)
#define rep0(n) rep1(aaaaa, n)
#define ov4(a, b, c, d, name, ...) name
#define rep(...) ov4(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define per(i, a, b) for (ll i = (a) - 1; i >= (b); i--)
#define fore(e, v) for (auto &&e : v)
#define all(a) begin(a), end(a)
#define sz(a) (ssize(a))
#define lb(v, x) (lower_bound(all(v), x) - begin(v))
#define eb emplace_back

template <typename T, typename S> bool chmin(T &a, const S &b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T, typename S> bool chmax(T &a, const S &b) {
  return a < b ? a = b, 1 : 0;
}
const int INF = 1e9 + 100;
const ll INFL = 3e18 + 100;
#define i128 __int128_t
struct _ {
  _() { cin.tie(0)->sync_with_stdio(0), cout.tie(0); }
} __;

void solve() {
  ll N, L, R;
  cin >> N >> L >> R;
  if (N == 1) {
    cout << "-1\n";
    return;
  }
  vector<pll> factor;
  ll t = 2;
  ll N2 = N;
  while (t * t <= N) {
    if (N % t == 0) {
      ll cnt = 0;
      while (N % t == 0) {
        cnt++;
        N /= t;
      }
      factor.push_back(pll{t, cnt});
    }
    t++;
  }
  if (N != 1)
    factor.push_back(pll{N, 1});
  vector<vl> divisor((1 << sz(factor)), vl());
  divisor[0].push_back(1);
  rep(i, 1 << sz(factor)) {
    rep(j, sz(factor)) {
      if (i >> j & 1)
        continue;
      if (!divisor[i | (1 << j)].empty())
        continue;
      ll p = 1;
      rep(e, factor[j].second + 1) {
        for (auto v : divisor[i]) {
          divisor[i | (1 << j)].push_back(v * p);
        }
        p *= factor[j].first;
      }
    }
  }
  fore(v, divisor) { sort(all(v)); }
  // cerr << "divisor:\n";
  // for (auto v : divisor) {
  //   fore(i, v) cerr << i << ' ';
  //   cerr << endl;
  // }
  vl ppow(sz(factor), 1);
  rep(i, sz(factor)) { rep(j, factor[i].second) ppow[i] *= factor[i].first; }
  using al3 = array<ll, 3>;
  auto dfs = [&](auto self, int idx, ll v1, ll v2, ll v3, int s1, int s2,
                 int s3) -> pair<al3, bool> {
    // rep(i, sz(factor)) cerr << (s1 >> i & 1);
    // cerr << " ";
    // rep(i, sz(factor)) cerr << (s2 >> i & 1);
    // cerr << " ";
    // rep(i, sz(factor)) cerr << (s3 >> i & 1);
    // cerr << endl;
    // cerr << v1 << ' ' << v2 << ' ' << v3 << endl;
    if (idx == sz(factor)) {
      vl v1m, v2m, v3m;
      auto l1 = lb(divisor[s2 | s3], (L + v1 - 1) / v1);
      while (l1 < sz(divisor[s2 | s3]) && sz(v1m) < 3 &&
             divisor[s2 | s3][l1] * v1 <= R) {
        v1m.push_back(divisor[s2 | s3][l1]);
        l1++;
      }
      auto l2 = lb(divisor[s1 | s3], (L + v2 - 1) / v2);
      while (l2 < sz(divisor[s1 | s3]) && sz(v2m) < 3 &&
             divisor[s1 | s3][l2] * v2 <= R) {
        v2m.push_back(divisor[s1 | s3][l2]);
        l2++;
      }
      auto l3 = lb(divisor[s1 | s2], (L + v3 - 1) / v3);
      while (l3 < sz(divisor[s1 | s2]) && sz(v3m) < 3 &&
             divisor[s1 | s2][l3] * v3 <= R) {
        v3m.push_back(divisor[s1 | s2][l3]);
        l3++;
      }
      for (auto vv1 : v1m) {
        for (auto vv2 : v2m) {
          for (auto vv3 : v3m) {
            al3 ans{vv1 * v1, vv2 * v2, vv3 * v3};
            sort(all(ans));
            if (ans[0] != ans[1] && ans[1] != ans[2]) {
              return make_pair(ans, true);
            }
          }
        }
      }
      return make_pair(al3{0, 0, 0}, false);
    }

    auto ret1 =
        self(self, idx + 1, v1 * ppow[idx], v2, v3, s1 | (1 << idx), s2, s3);
    if (ret1.second) {
      return ret1;
    }
    auto ret2 =
        self(self, idx + 1, v1, v2 * ppow[idx], v3, s1, s2 | (1 << idx), s3);
    if (ret2.second) {
      return ret2;
    }
    auto ret3 =
        self(self, idx + 1, v1, v2, v3 * ppow[idx], s1, s2, s3 | (1 << idx));
    if (ret3.second) {
      return ret3;
    }
    return make_pair(al3{0, 0, 0}, false);
  };
  auto [ans, ok] = dfs(dfs, 1, ppow[0], 1, 1, 1, 0, 0);
  if (ok) {
    cout << ans[0] << ' ' << ans[1] << ' ' << ans[2] << '\n';
    assert(lcm(ans[0], lcm(ans[1], ans[2])) == N2);
    assert(ans[0] >= L);
    assert(ans[2] <= R);
  } else {
    cout << "-1\n";
  }
}

int main() {
  int T;
  cin >> T;
  rep(T) solve();
}

/*
1
73513440 1 73513440
*/