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

• 問題: No.3663 LCM Decomposition
• ユーザー: lif4635
• 提出日時: 2026-08-30 16:25:21
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0)
• 結果: AC
• 実行時間: 210 ms / 1,000 ms
• コード長: 3,376 bytes
• コンパイル時間: 4,235 ms
• コンパイル使用メモリ: 384,124 KB
• 実行使用メモリ: 6,272 KB
• 最終ジャッジ日時: 2026-08-30 16:25:38
• 合計ジャッジ時間: 6,615 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge3_0

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

ソースコード

// # pragma GCC target("avx2")
// # pragma GCC optimize("O3")
// # pragma GCC optimize("unroll-loops")
#ifdef harurun
#define debug(x) cerr<<#x<<": "<<x<<endl
#else
#define debug(x)
#endif
#include <bits/stdc++.h>
using namespace std;
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
// using mint = modint1000000007;
// using mint = double;
#endif

//define
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<long long , long long>;
using vi = vector<int>;
using vll = vector<long long>;

#define rep(i,l,r) for (int i = (int)(l); i < (int)(r); i++)
#define rrep(i,l,r) for (int i = (int)(r-1); i >= (int)(l); i--)
#define len(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define elif else if
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
const int inf = 1e9;
const long long infl = 1LL<<60;
const int mod = 998244353;
ll pow(ll a, ll b, ll p){ ll ans = 1; while(b){ if(b & 1) (ans *= a) %= p; (a *= a) %= p; b /= 2; } return ans; }
template<class T, class U> bool chmin(T& a, const U& b){ if(a > T(b)){ a = b; return 1; } return 0; }
template<class T, class U> bool chmax(T& a, const U& b){ if(a < T(b)){ a = b; return 1; } return 0; }
template <class T>
using spq = priority_queue<T, vector<T>, greater<T>>;

template<class T>istream& operator>>(istream& i, vector<T>& v) {for(int j = 0; j < (int)(v).size(); j++) i >> v[j]; return i;}
struct IoSetup {
    IoSetup() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(15);
        cerr << fixed << setprecision(15);
    }
} iosetup;

vi pri(int n){
    int p = 2;
    vi r;
    while(p * p <= n){
        int c = 1;
        while (n % p == 0){
            n /= p; c *= p;
        }
        if (c != 1){
            r.pb(c);
        }
        p++;
    }
    if (n != 1){
        r.pb(n);
    }
    return r;
}

vi div(int n){
    vi d;
    int i = 1;
    while (i * i <= n){
        if (n % i == 0){
            d.pb(i);
            if (i != n / i){
                d.pb(n / i);
            }
        }
        i++;
    }
    sort(all(d));
    return d;
}

void solve(){
    int n, l, r; cin >> n >> l >> r;
    vi ds = div(n);
    vi q = pri(n);

    int d = len(q);
    vector<pii> ok;
    for (auto x : ds){
        if (l <= x and x <= r){
            int bit = 0;
            rep(i, 0, d){
                if (x % q[i] == 0){
                    bit |= 1 << i;
                }
            }
            ok.pb({x, bit});
        }
    }
    vector dp(4, vector<array<int, 3>>(1 << d));
    rep(i, 0, 4){
        rep(s, 0, 1 << d){
            rep(j, 0, 3){
                dp[i][s][j] = -1;
            }
        }
    }
    dp[0][0][0] = 0;

    for (auto [x, b] : ok){
        rrep(k, 0, 3){
            rep(s, 0, 1 << d){
                if (dp[k][s][0] != -1){
                    dp[k+1][s|b] = dp[k][s];
                    dp[k+1][s|b][k] = x; 
                }
            }
        }
    }
    array<int, 3> ans = dp[3][(1<<d) - 1];
    if (ans[0] == -1){
        cout << -1 << endl;
    }else{
        cout << ans[0] << " " << ans[1] << " " << ans[2] << endl;
    }
    // cout << -1 << endl;
    return ;
}


int main(){
    int t;
    cin >> t;
    // t = 1;
    while(t--) solve();
    return 0;
}