結果

問題 No.3663 LCM Decomposition
コンテスト
ユーザー aqua
提出日時 2026-09-02 21:29:14
言語 C++23
(gcc 15.3.0 + boost 1.92.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 2,689 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,511 ms
コンパイル使用メモリ 351,664 KB
実行使用メモリ 9,792 KB
最終ジャッジ日時 2026-09-02 21:29:23
合計ジャッジ時間 5,035 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4 WA * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

using ll = long long;

bool chmin(auto &a, auto b) { return a > b ? a = b, 1 : 0; }
bool chmax(auto &a, auto b) { return a < b ? a = b, 1 : 0; }

void solve() {
    int N, L, R; cin >> N >> L >> R;
    vector<int> pp, d{1, N};
    for (int i = 2, M = N; i * i <= N; ++i) {
        int p = 1;
        while (M % i == 0) {
            M /= i;
            p *= i;
        }
        if (p > 1) pp.emplace_back(p);

        if (N % i == 0) {
            d.emplace_back(i);
            d.emplace_back(N / i);
        }
    }
    sort(d.begin(), d.end());
    d.erase(unique(d.begin(), d.end()), d.end());

    vector<vector<int>> S(1 << pp.size());
    for (int i = 0; i < d.size(); ++i) {
        if (d[i] < L || R < d[i]) continue;
        int mask = 0;
        for (int j = 0; j < pp.size(); ++j) mask += (d[i] % pp[j] == 0) << j;
        if (S[mask].size() < 3) S[mask].emplace_back(d[i]);
    }
    for (int i = (1 << pp.size()) - 1; i > 0; ) {
        int j = (i - 1) & ((1 << pp.size()) - 1);
        for (int k = 0; k < S[i].size() && S[j].size() < 3; ++k) {
            if (S[j].size() && (S[i][k] == S[j][0] || S[i][k] == S[j].back())) continue;
            S[j].emplace_back(S[i][k]);
        }
        i = j;
    }
    vector<int> ans;
    int prod = 1;
    for (int i = 0; i < pp.size(); ++i) prod *= 3;
    for (int i = 0; i < prod; ++i) {
        ans.clear();
        int a = 0, b = 0, c = 0;
        int cur = i;
        for (int j = pp.size(), mul = prod / 3; j--; cur %= mul, mul /= 3) {
            if (cur / mul == 0) a += 1 << j;
            else if (cur / mul == 1) b += 1 << j;
            else c += 1 << j;
        }
        if (S[a].size()) ans.emplace_back(S[a][0]);
        else continue;
        if (S[b].size() && S[b][0] != ans[0]) ans.emplace_back(S[b][0]);
        else if (S[b].size() >= 2 && S[b][1] != ans[0]) ans.emplace_back(S[b][1]);
        else if (S[b].size() == 3 && S[b][2] != ans[0]) ans.emplace_back(S[b][2]);
        else continue;
        if (S[c].size() && S[c][0] != ans[0] && S[c][0] != ans[1]) {
            ans.emplace_back(S[c][0]);
        } else if (S[c].size() >= 2 && S[c][1] != ans[0] && S[c][1] != ans[1]) {
            ans.emplace_back(S[c][1]);
        } else if (S[c].size() == 3 && S[c][2] != ans[0] && S[c][2] != ans[1]) {
            ans.emplace_back(S[c][2]);
        } else {
            continue;
        }
        sort(ans.begin(), ans.end());
        for (int j = 0; j < 3; ++j) cout << ans[j] << " \n"[j == 2];
        return;
    }
    cout << -1 << '\n';
}

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

    int T; cin >> T;
    while (T--) solve();
}
0