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

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

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

ソースコード

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <format>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>
int main() {
    using namespace std;
    using lint = long long;
    auto solve = [] {
        lint n, l, r;
        cin >> n >> l >> r;
        vector<tuple<lint, int, lint>> pe;
        {
            lint nn = n;
            for (lint p = 2; p * p <= nn; ++p) {
                if (nn % p) continue;
                int e = 0;
                int p_e = 1;
                while (nn % p == 0) {
                    nn /= p;
                    e++;
                    p_e *= p;
                }
                pe.emplace_back(p, e, p_e);
            }
            if (nn > 1) pe.emplace_back(nn, 1, nn);
        }

        int m = pe.size();
        vector<lint> divisors0{1};
        {
            for (auto [p, e, p_e] : pe) {
                int s = divisors0.size();
                for (int i = 0; i < s; ++i)
                    for (int pei = p; pei <= p_e; pei *= p)
                        divisors0.push_back(divisors0[i] * pei);
            }
        }
        if (divisors0.size() < 3) {
            puts("-1");
            return;
        }
        vector<vector<lint>> ok(1 << m);
        for (auto d : divisors0) {
            if (d < l || d > r) continue;
            int bit = 0;
            for (int i = 0; i < m; ++i) {
                auto [p, e, p_e] = pe[i];
                if (d % p_e == 0) bit |= 1 << i;
            }
            if (ok[bit].size() < 3) {
                for (int sub = 0;; sub = (sub - bit) & bit) {
                    if (ok[sub].size() < 3) ok[sub].push_back(d);
                    if (sub == bit) break;
                }
            }
        }
        // for (int i = 0; i < (1 << m); ++i) {
        //     if (ok[i].empty()) continue;
        //     cout << format("{:09b}:", i);
        //     for (auto e : ok[i]) cout << " " << e;
        //     cout << "\n";
        // }
        auto shout = [&](lint a, lint b, lint c) {
            if (a == b || a == c || b == c) return false;
            vector ans{a, b, c};
            ranges::sort(ans);
            if (!(l <= ans[0])) return false;
            if (!(ans[0] < ans[1])) return false;
            if (!(ans[1] < ans[2])) return false;
            if (!(ans[2] <= r)) return false;
            lint ll = lcm(lcm(ans[0], ans[1]), ans[2]);
            if (!(ll == n)) return false;
            cout << ans[0] << " " << ans[1] << " " << ans[2] << "\n";
            return true;
        };
        int full = (1 << m) - 1;
        for (int bit_a = 1 << m - 1; bit_a < (1 << m); ++bit_a) {
            if (ok[bit_a].empty()) continue;
            int rem = bit_a ^ full;
            for (int bit_b = 0;; bit_b = (bit_b - full) & full) {
                int bit_c = bit_b ^ rem;
                if (!ok[bit_b].empty() && !ok[bit_c].empty()) {
                    for (lint da : ok[bit_a])
                        for (lint db : ok[bit_b])
                            for (lint dc : ok[bit_c]) {
                                if (shout(da, db, dc)) return;
                            }
                }
                if (bit_b == full) break;
            }
        }
        puts("-1");
    };

    int ct;
    cin >> ct;

    while (ct--) {
        solve();
    }
}