結果

問題 No.3663 LCM Decomposition
コンテスト
ユーザー wasd314
提出日時 2026-08-30 16:05:41
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.92.0)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 2,891 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,544 ms
コンパイル使用メモリ 197,384 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2026-08-30 16:05:52
合計ジャッジ時間 3,085 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 9 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <algorithm>
#include <cstdio>
#include <format>
#include <iostream>
#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;
        for (lint p = 2; p * p <= n; ++p) {
            if (n % p) continue;
            int e = 0;
            int p_e = 1;
            while (n % p == 0) {
                n /= p;
                e++;
                p_e *= p;
            }
            pe.emplace_back(p, e, p_e);
        }
        if (n > 1) pe.emplace_back(n, 1, n);

        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;
            }
            ok[bit].push_back(d);
        }
        // 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";
        // }

        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 (da == db || da == dc || db == dc) continue;
                                vector ans{da, db, dc};
                                ranges::sort(ans);
                                cout
                                    << ans[0]
                                    << " "
                                    << ans[1]
                                    << " "
                                    << ans[2]
                                    << "\n";
                                return;
                            }
                }
                if (bit_b == full) break;
            }
        }
        puts("-1");
    };

    int ct;
    cin >> ct;

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