#1181603 (D) No.3663 LCM Decomposition

• 問題: No.3663 LCM Decomposition
• ユーザー: InTheBloom
• 提出日時: 2026-08-30 17:04:43
• 言語: D (dmd 2.113.0)
• 結果: AC
• 実行時間: 293 ms / 1,000 ms
• コード長: 5,405 bytes
• コンパイル時間: 3,847 ms
• コンパイル使用メモリ: 211,968 KB
• 実行使用メモリ: 6,272 KB
• 最終ジャッジ日時: 2026-08-30 17:04:52
• 合計ジャッジ時間: 6,833 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge3_0

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

ソースコード

import std;

void main () {
    int caseNum = readln.chomp.to!int;
    foreach (caseId; 0 .. caseNum) {
        int N, L, R;
        readln.read(N, L, R);

        if (N == 1) {
            writeln(-1);
            continue;
        }

        // a, b, cそれぞれ約数が必要条件
        auto pfs = primeFactors(N);
        auto divs = divisors(N);

        divs = divs.arrayBSearch!((v) => v < L)[1].arrayBSearch!((v) => v <= R)[0];

        if (divs.length < 3) {
            writeln(-1);
            continue;
        }

        auto S = new int[](divs.length);
        foreach (i; 0 .. divs.length) {
            foreach (idx, p; pfs.enumerate(0)) {
                long x = p[0] ^^ p[1];
                if (divs[i] % x == 0) {
                    S[i] |= 1 << idx;
                }
            }
        }

        auto cnt = new int[](1 << pfs.length);
        foreach (s; S) {
            if (cnt[s] == 0) {
                cnt[s]++;
            }
        }

        foreach (i; 0 .. pfs.length) {
            foreach (s; 0 .. pfs.length) {
                if (0 < (s & (1 << i))) {
                    cnt[s ^ (1 << i)] += cnt[s];
                }
            }
        }

        int[int] use;
        foreach (s; 0 .. 1 << pfs.length) {
            if (cnt[s] == 1) {
                use[s]++;
            }
        }

        auto vs = new Tuple!(int, int)[](0);
        foreach (i, s; S.enumerate(0)) {
            if (s in use) {
                vs ~= tuple(s, cast(int)(divs[i]));
                use.remove(s);
            }
        }

        auto dp = new Tuple!(int, int)[][](4, 1 << pfs.length);
        foreach (d; dp) {
            d[] = tuple(-int.max, 0);
        }
        dp[0][0] = tuple(-1, 0);

        foreach (val; vs) {
            foreach (i; 0 .. 4) {
                foreach (set; 0 .. 1 << pfs.length) {
                    if (dp[i][set][0] == -int.max) {
                        continue;
                    }

                    if (i + 1 <= 3 && set < (set | val[0])) {
                        dp[i + 1][set | val[0]] = tuple(val[1], set);
                    }
                }
            }
        }

        const int bt = (1 << pfs.length) - 1;
        bool ok = false;
        int[int] ans;

        foreach (i; 1 .. 4) {
            int cur = bt;
            int ci = i;
            if (0 < dp[ci][cur][0]) {
                while (cur != 0) {
                    ans[dp[ci][cur][0]]++;
                    cur = dp[ci][cur][1];
                    ci--;
                }
                ok = true;
                break;
            }
        }
        if (!ok) {
            writeln(-1);
            continue;
        }
        foreach (d; divs) {
            if (ans.length == 3) {
                break;
            }
            ans[cast(int)(d)]++;
        }

        auto used = ans.keys();
        used.sort;

        writefln("%(%s %)", used);
    }
}

void read (T...) (string S, ref T args) {
    import std.conv : to;
    import std.array : split;
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}

import std.typecons : Tuple, tuple;

Tuple!(long, int)[] primeFactors (long N) {
    import std.format : format;
    import std.exception;
    enforce(2 <= N && N <= 10L^^16, format("The argument %s is out of the allowable range. The valid range is [2, 10^16].", N));

    Tuple!(long, int)[] res;
    foreach (i; 2..N) {
        if (N < 1L*i*i) break;
        if (N % i != 0) continue;

        int count = 0;
        while (N % i == 0) {
            N /= i;
            count++;
        }

        res ~= tuple(1L*i, count);
    }

    if (1 < N) res ~= tuple(N, 1);

    return res;
}

long[] divisors (ulong N)
in {
    import std.format : format;
    assert(1 <= N && N <= 10L^^16, format("The argument %s is out of the allowable range. The valid range is [2, 10^16].", N));
}
do {
    import std.algorithm : sort;
    long[] res;
    foreach (i; 1..N + 1) {
        if (N < 1L * i * i) break;
        if (N % i == 0) {
            res ~= i;
            if (1L * i * i < N) res ~= N / i;
        }
    }

    res.sort;
    return res;
}

/// 配列特化二分探索
/// fun: T -> boolが必要。また、一度falseになったら後ろが必ずfalseになるような述語を仮定。
/// fun: (int, T) -> boolにも対応済み
/// 戻り値はスライス2個。
/// それぞれB1, B2としたとき、
/// B1の要素はfun(b1)がtrue
/// B2の要素はfun(b2)がfalse

import std.traits;

T[][2] arrayBSearch (alias fun, T) (T[] A)
if ((__traits(compiles, fun(T.init)) || __traits(compiles, fun(int.init, T.init)))
    && (is(typeof(fun(T.init)) == bool) || is(typeof(fun(int.init, T.init)) == bool))
    ) {
    if (A.length == 0) {
        return [[], []];
    }
    static if (__traits(compiles, fun(int.init, T.init))) {
        bool fi = fun(0, A[0]);
    }
    else {
        bool fi = fun(A[0]);
    }
    if (!fi) {
        return [[], A[]];
    }

    int l = 0, r = cast(int)(A.length);
    while (1 < r - l) {
        int mid = (l + r) / 2;
        static if (__traits(compiles, fun(int.init, T.init))) {
            bool ok = fun(mid, A[mid]);
        }
        else {
            bool ok = fun(A[mid]);
        }

        if (ok) {
            l = mid;
        }
        else {
            r = mid;
        }
    }
    return [A[0 .. r], A[r .. $]];
}