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

• 問題: No.3663 LCM Decomposition
• ユーザー: syndrome
• 提出日時: 2026-08-30 14:11:36
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0)
• 結果: AC
• 実行時間: 180 ms / 1,000 ms
• コード長: 5,014 bytes
• コンパイル時間: 2,900 ms
• コンパイル使用メモリ: 368,164 KB
• 実行使用メモリ: 6,272 KB
• 最終ジャッジ日時: 2026-08-30 14:11:51
• 合計ジャッジ時間: 5,672 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

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

ソースコード

// (◕ᴗ◕✿)

// #pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define srep(i, s, n) for (ll i = s; i < (n); i++)
#define len(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
using namespace std;
template<typename T> using vc = vector<T>;
template<typename T> using vv = vc<vc<T>>;
template<typename T> using vvv = vv<vc<T>>;
using vi = vc<int>;using vvi = vv<int>; using vvvi = vv<vi>;
using ll = long long;using vl = vc<ll>;using vvl = vv<ll>; using vvvl = vv<vl>;
using ld = long double; using vld = vc<ld>; using vvld = vc<vld>; using vvvld = vc<vvld>;
using uint = unsigned int;
using ull = unsigned long long;
const ld pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
// const ll mod = 1000000007;
const ll mod = 998244353;
inline bool inside(ll y, ll x, ll H, ll W) {return 0 <= (y) and (y) < (H) and 0 <= (x) and (x) < (W); }

#define debug(var) do { cerr << #var << " :\n"; view(var); } while(0)
template<typename T>void view(const T& e) {cerr << e;}
template<typename T1, typename T2>void view(const pair<T1, T2>& p) {cerr << "{" << p.first << ", " << p.second << "}";}
template<typename T>void view(const vc<T>& v) {for (const auto& e : v) {view(e);cerr << " ";} cerr << endl;}
template<typename T>void view(const vv<T>& vv) {for (const auto& v : vv) {view(v);} cerr << endl;}
template<typename T>void view(const set<T>& s) {for (const auto& e : s) {view(e);cerr << " ";} cerr << endl;}
template<typename T>void view(const multiset<T>& s) {for (const auto& e : s) {view(e);cerr << " ";} cerr << endl;}
template<typename T>void view(const unordered_set<T>& s) {for (const auto& e : s) {view(e);cerr << " ";} cerr << endl;}
template<typename T1, typename T2>void view(const map<T1, T2>& mp){for (const auto& e : mp) {view(e);cerr << " ";} cerr << endl;}

unsigned int randxor(){
    static unsigned int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    unsigned int t;
    t = (x ^ (x << 11)); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
int randint(int a, int b) {return(a + randxor() % (b - a));}

vc<ll> factorization(ll &N){
    vc<ll> factors;
    ll tmp = N;
    for (ll i = 2; i * i <= N + 1; i++){
        if (tmp % i == 0){
            ll cnt = 1;
            while (tmp % i == 0){
                tmp /= i;
                cnt *= i;
            }
            factors.push_back(cnt);
        }
    }
    if (tmp != 1){
        factors.push_back(tmp);
    }
    if (len(factors) == 0){
        factors.push_back(N);
    }
    return factors;
}

bool solve(){
    ll N, L, R; cin >> N >> L >> R;
    auto fact = factorization(N);
    vl element, candidate;
    vl bit;
    vl bits(1 << len(fact), -1);
    int fullbit = 0, msk = (1 << len(fact)) - 1;
    // debug(fact);
    auto push = [&](ll p){
        int mybit = 0;
        rep(i, len(fact)) if (p % fact[i] == 0){
            mybit |= (1 << i);
        }
        if (mybit == 0) candidate.push_back(p);
        else{
            element.push_back(p);
            bit.push_back(mybit);
        }
        fullbit |= mybit;
        bits[mybit] = p;
        // cout << p << ' ' << mybit << endl;
    };
    for (ll p = 1; p * p <= N; p++) if (N % p == 0){
        if (L <= p && p <= R) push(p);
        if (N / p != p && L <= N / p && N / p <= R) push(N / p);
    }

    if (fullbit != msk){
        cout << -1 << endl;
        return true;
    }

    rep(k, len(fact)) rep(i, 1 << len(fact)) if (~i >> k & 1) bits[i] = max(bits[i ^ (1 << k)], bits[i]);
    bits[0] = -1;

    rep(i, 2000){
        int a = randint(0, len(element)), b = randint(0, len(element));
        if (bit[a] == msk && len(candidate) >= 2){
            vl ans = {element[a]};
            rep(j, 2)ans.push_back(candidate[j]);
            sort(all(ans));
            cout << ans[0] << ' ' << ans[1] << ' ' << ans[2] << endl;
            return true;
        }
        if (a == b) continue;
        if ((bit[a] | bit[b]) == msk && (len(candidate) >= 1 || len(element) >= 3)){
            vl ans = {element[a], element[b]};
            if (len(candidate)) ans.push_back(candidate[0]);
            else rep(i, 3) if (i != a && i != b){
                ans.push_back(element[i]);
                break;
            }
            sort(all(ans));
            cout << ans[0] << ' ' << ans[1] << ' ' << ans[2] << endl;
            return true;
        }
        if (bits[msk ^ (bit[a] | bit[b])] != -1){
            vl ans = {element[a], element[b], bits[msk ^ (bit[a] | bit[b])]};
            sort(all(ans));
            assert(ans[0] != ans[1] && ans[1] != ans[2]);
            cout << ans[0] << ' ' << ans[1] << ' ' << ans[2] << endl;
            return true;
        }
    }
    cout << -1 << endl;
    
    return true;
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--) solve();

    // while (solve());
}