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

• 問題: No.3663 LCM Decomposition
• ユーザー: shinchan
• 提出日時: 2026-08-30 15:19:27
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0)
• 結果: AC
• 実行時間: 218 ms / 1,000 ms
• コード長: 5,828 bytes
• コンパイル時間: 2,865 ms
• コンパイル使用メモリ: 360,192 KB
• 実行使用メモリ: 6,272 KB
• 最終ジャッジ日時: 2026-08-30 15:19:34
• 合計ジャッジ時間: 5,606 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_1

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

ソースコード

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

#define all(v) (v).begin(),(v).end()
#define pb emplace_back
#define rep(i, n) for(int i=0;i<(n);i++)
#define foa(e, v) for(auto& e : v)
#define dout(a) cout<<fixed<<setprecision(10)<<a<<'\n';
#define Cout(a) cout<<a<<'\n';

using ll = long long;
using ld = long double;
using Int = __int128;
template <class T> using pqr = priority_queue<T, vector<T>, greater<T>>;

template <typename T1, typename T2> inline bool chmax(T1 &a, T2 b) {
    bool compare = a < b;
    if(compare) a = b;
    return compare;
}
template <typename T1, typename T2> inline bool chmin(T1 &a, T2 b) {
    bool compare = a > b;
    if(compare) a = b;
    return compare;
}
template <typename T> inline T back(std::set<T> &s) {
    return *s.rbegin();
}
template <typename T> inline T back(std::multiset<T> &s) {
    return *s.rbegin();
}
template <typename T> inline T pop_back(std::set<T> &s) {
    auto it = prev(s.end());
    T val = *it;
    s.erase(it); 
    return val;
}
template <typename T> inline T pop_back(std::multiset<T> &s) {
    auto it = prev(s.end());
    T val = *it;
    s.erase(it); 
    return val;
}

const int dy[8] = {-1, 0, 0, 1, 1, -1, 1, -1};
const int dx[8] = {0, -1, 1, 0, -1, -1, 1, 1};

const ll MOD7 = 1000000007, MOD998 = 998244353, INF = (3LL << 59);
const int inf = 1 << 30;
const char br = '\n';

long long modinv(long long a, long long MOD) {
    long long b = MOD, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; std::swap(a, b);
        u -= t * v; std::swap(u, v);
    }
    u %= MOD; 
    if (u < 0) u += MOD;
    return u;
}

long long modpow(long long a, long long n, long long MOD) {
    long long res = 1;
    a %= MOD;
    if(n < 0) {
        n = -n;
        a = modinv(a, MOD);
    }
    while (n > 0) {
        if (n & 1) res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}

vector<pair<ll, ll>> primes(ll n) {
    ll m = n;
    vector<pair<ll, ll>> v;
    for(ll i = 2; i * i <= n; i ++) {
        if(m % i == 0) {
            ll num = 0;
            while(m % i == 0) {
                m /= i;
                num ++;
            }
            v.pb(i, num);
        }
    }
    if(m > 1) v.pb(m, 1);
    return v;
}

vector<ll> divisor(ll n) {
    vector<ll> v;
    for(ll i = 1; i * i <= n; i++) {
        if(n % i == 0) {
            if(i * i != n) v.pb(n / i);
            v.pb(i);
        }
    }
    return v;
}

template <typename T> void fzt(vector<T>& f) {
    int n = f.size();
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j ++) {
            if ((j & i) == 0) f[j | i] += f[j];
        }
    }
}
template <typename T> void ifzt(vector<T>& f) {
    int n = f.size();
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j ++) {
            if ((j & i) == 0) f[j | i] -= f[j];
        }
    }
}
void solve() {
    ll n, le, ri; cin >> n >> le >> ri;
    auto vec2 = divisor(n);
    vector<ll> v;
    foa(e, vec2) if(le <= e and e <= ri) v.pb(e);

    
    
    auto vec = primes(n);
    int sz = vec.size();
    vector<ll> maxs;
    for(auto [x, y] : vec) maxs.pb(modpow(x, y, INF));

    int szv = v.size();
    vector<int> bits(szv, 0);
    vector<ll> now(1 << sz, -1);
    rep(i, szv) {
        rep(j, sz) {
            if(v[i] % maxs[j] == 0) bits[i] |= 1 << j;
        }
        now[bits[i]] = i; // v[i]
    }

    vector<ll> dp1(1 << sz, 0);
    rep(i, szv) {
        dp1[bits[i]] ++;
    }
    fzt(dp1);
    vector<ll> dp2(1 << sz, 0);
    rep(i, 1 << sz) dp2[i] = dp1[i] * dp1[i];
    
    vector<ll> dp3(1 << sz, 0);
    rep(i, 1 << sz) dp3[i] = dp2[i] * dp1[i];
    ifzt(dp1); ifzt(dp2); ifzt(dp3);
    
    if(!dp3[(1 << sz) - 1]) {
        cout << -1 << endl;
    } else {

        int mask = (1 << sz) - 1;
        vector<int> ansv;
        vector<int> dp(1 << sz, -1);
        rep(i, 1 << sz) {
            if(dp1[i]) dp[i] = i;
        }

        for(int bit = mask; bit >= 0; bit --) {
            rep(i, 1 << sz) {
                if(bit >> i & 1) {
                    chmax(dp[bit ^ (1 << i)], dp[bit]);
                }
            }
        }
        int num = mask;
        rep(i, 1 << sz) {
            if(dp2[i] and dp[num ^ i] >= 0) {
                ansv.pb(num ^ i);
                num = i;
                break;
            }
        }
        rep(i, 1 << sz) {
            if(dp1[i] and dp[num ^ i] >= 0) {
                ansv.pb(num ^ i);
                num = i;
                break;
            }
        }
        ansv.pb(num);
        sort(all(ansv));
        vector<vector<ll>> can(3);
        foa(e, v) {
            int val = 0;
            rep(j, sz) {
                if(e % maxs[j] == 0) val |= 1 << j;
            }
            rep(i, 3) if((val & ansv[i]) == ansv[i]) {
                can[i].pb(e);
            }
        }
        // rep(i, 3) {
            // foa(e, can[i]) cout << e << " ";
            // cout << endl;
        // }
        rep(i, 3) {
            if((int)can[i].size() > 3) {
                can[i].resize(3);
            }
            
        }
        vector<ll> ans;
        foa(e1, can[0]) foa(e2, can[1]) foa(e3, can[2]) {
            if(e1 != e2 and e2 != e3 and e1 != e3) {
                vector<ll> s{e1, e2, e3};
                sort(all(s));
                foa(e, s) cout << e << " ";
                cout << endl;
                return;
            }
        }
        cout << -1 << endl;

        

    }
    
    
    
    
    // rep(bit, 1 << sz) {
    //     for(int bit2 = bit; bit2 > 0; bit2 = (bit2 - 1) & bit) {
    //         if(chmin(dp[bit], dp[bit2] + dp[bit]))
    //     }
    // }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int testcase = 1; 
    cin >> testcase;
    while(testcase --) solve();

    return 0;
}