#1179616 (C++17) No.3663 LCM Decomposition

• 問題: No.3663 LCM Decomposition
• ユーザー: sepa38
• 提出日時: 2026-08-28 20:47:56
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0)
• 結果: TLE
• 実行時間: -
• コード長: 4,283 bytes
• コンパイル時間: 2,653 ms
• コンパイル使用メモリ: 215,072 KB
• 実行使用メモリ: 6,272 KB
• 最終ジャッジ日時: 2026-08-30 13:05:28
• 合計ジャッジ時間: 6,802 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

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

ソースコード

#include <iostream>
#include <vector>
#include <map>
#include <numeric>
#include <algorithm>
#include <random>
#include <atcoder/all>

using namespace std;
using u64 = unsigned long long;
using u128 = __uint128_t;

// a^b mod m
u64 pow_mod(u64 a, u64 b, u64 m) {
    u64 res = 1;
    a %= m;
    while (b) {
        if (b & 1) res = (u64)((u128)res * a % m);
        a = (u64)((u128)a * a % m);
        b >>= 1;
    }
    return res;
}

// Miller-Rabin 素数判定
bool is_prime(u64 n) {
    if (n < 2) return false;
    for (u64 p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
        if (n % p == 0) return n == p;
    }
    u64 d = n - 1;
    int s = __builtin_ctzll(d);
    d >>= s;
    for (u64 a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
        u64 x = pow_mod(a, d, n);
        if (x == 1 || x == n - 1) continue;
        bool ok = false;
        for (int i = 0; i < s - 1; i++) {
            x = (u64)((u128)x * x % n);
            if (x == n - 1) {
                ok = true;
                break;
            }
        }
        if (!ok) return false;
    }
    return true;
}

mt19937_64 rng(1333); // 乱数生成器 (グローバルに1つ持つ)

// Pollard's rho 法
u64 pollard(u64 n) {
    if (n % 2 == 0) return 2;
    while (true) {
        u64 c = rng() % (n - 1) + 1;
        auto f = [&](u64 x) { return (u64)(((u128)x * x + c) % n); };
        u64 x = 2, y = 2, d = 1;
        while (d == 1) {
            x = f(x);
            y = f(f(y));
            d = std::gcd(x > y ? x - y : y - x, n);
        }
        if (d != n) return d;
    }
}

// 素因数分解
map<long long, int> factorize(long long n) {
    map<long long, int> res;
    vector<long long> stack;
    if (n > 1) stack.push_back(n);
    while (!stack.empty()) {
        long long m = stack.back();
        stack.pop_back();
        if (is_prime(m)) {
            res[m]++;
        } else {
            long long d = pollard(m);
            stack.push_back(d);
            stack.push_back(m / d);
        }
    }
    return res;
}

long long p_pow(long long base, int exp) {
    long long res = 1;
    for (int i = 0; i < exp; ++i) res *= base;
    return res;
}

void solve() {
    long long n, l, r;
    cin >> n >> l >> r;

    if (n == 1) {
        cout << -1 << "\n";
        return;
    }

    auto fac = factorize(n);

    vector<long long> d = {1};
    vector<long long> ls;

    for (auto const& [pi, exp] : fac) {
        ls.push_back(p_pow(pi, exp));
        long long x = 1;
        int ln = d.size();
        for (int i = 0; i < exp; ++i) {
            x *= pi;
            for (int j = 0; j < ln; ++j) {
                d.push_back(d[j] * x);
            }
        }
    }

    sort(d.begin(), d.end());

    vector<long long> bc;
    for (long long v : d) {
        if (l <= v && v <= r) {
            bc.push_back(v);
        }
    }
    // d がソート済みなので bc も自動的にソートされた状態になる

    vector<long long> ans = {-1, -1, -1};

    for (int ic = (int)bc.size() - 1; ic >= 0; --ic) {
        long long c = bc[ic];
        for (int ib = ic - 1; ib >= 0; --ib) {
            long long b = bc[ib];

            long long x = 1; // a は x の倍数
            for (long long v : ls) {
                if (c % v != 0 && b % v != 0) {
                    x *= v;
                }
            }

            if (x >= b) continue;

            // a = x*k とおく
            long long kmin = (l + x - 1) / x;
            long long kmax = (b - 1) / x;

            auto le = lower_bound(d.begin(), d.end(), kmin);
            auto ri = upper_bound(d.begin(), d.end(), kmax);

            long long rem = n / x;

            for (auto it = le; it != ri; ++it) {
                long long k = *it;
                if (rem % k == 0) {
                    ans = {x * k, b, c};
                    break;
                }
            }

            if (ans[0] > 0) break;
        }
        if (ans[0] > 0) break;
    }

    if (ans[0] > 0) {
        cout << ans[0] << " " << ans[1] << " " << ans[2] << "\n";
    } else {
        cout << -1 << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}