結果

問題 No.2896 Monotonic Prime Factors
ユーザー InTheBloomInTheBloom
提出日時 2024-09-20 22:56:58
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 306 ms / 2,000 ms
コード長 7,835 bytes
コンパイル時間 2,798 ms
コンパイル使用メモリ 223,616 KB
実行使用メモリ 37,120 KB
最終ジャッジ日時 2024-09-20 22:57:09
合計ジャッジ時間 8,294 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 88 ms
35,200 KB
testcase_01 AC 87 ms
36,452 KB
testcase_02 AC 88 ms
35,200 KB
testcase_03 AC 88 ms
35,328 KB
testcase_04 AC 208 ms
36,864 KB
testcase_05 AC 227 ms
36,864 KB
testcase_06 AC 306 ms
36,992 KB
testcase_07 AC 208 ms
36,864 KB
testcase_08 AC 207 ms
37,120 KB
testcase_09 AC 226 ms
37,120 KB
testcase_10 AC 175 ms
36,608 KB
testcase_11 AC 132 ms
36,352 KB
testcase_12 AC 98 ms
36,096 KB
testcase_13 AC 184 ms
36,608 KB
testcase_14 AC 213 ms
36,736 KB
testcase_15 AC 93 ms
36,096 KB
testcase_16 AC 128 ms
36,480 KB
testcase_17 AC 105 ms
36,352 KB
testcase_18 AC 277 ms
36,992 KB
testcase_19 AC 107 ms
36,352 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std;

void main () {
    int Q = readln.chomp.to!int;

    const long MOD = 998244353;
    alias fac = PrimeModuloFactorial!MOD;
    fac.build(2 * 10 ^^ 6 + 10);

    alias ls = LinearSieve;
    ls.build(10 ^^ 5 + 10);

    int factor_count = 0;
    auto ans = new long[](Q);

    foreach (i; 0..Q) {
        int A, B; readln.read(A, B);
        factor_count += () {
            int res = 0;
            auto p = ls.prime_factors(A);
            foreach (v; p) {
                res += v[1].to!int;
            }
            return res;
        }();

        ans[i] = fac.binom(factor_count - 1, B - 1);
    }

    foreach (a; ans) writeln(a);
}

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));
    }
}

long mod_pow (long a, long x, const long MOD)
in {
    assert(0 <= x, "x must satisfy 0 <= x");
    assert(1 <= MOD, "MOD must satisfy 1 <= MOD");
    assert(MOD <= int.max, "MOD must satisfy MOD*MOD <= long.max");
}
do {
    // normalize
    a %= MOD; a += MOD; a %= MOD;

    long res = 1L;
    long base = a;
    while (0 < x) {
        if (0 < (x&1)) (res *= base) %= MOD;
        (base *= base) %= MOD;
        x >>= 1;
    }

    return res % MOD;
}

// check mod_pow
static assert(__traits(compiles, mod_pow(2, 10, 998244353)));

long mod_inv (const long x, const long MOD)
in {
    import std.format : format;
    assert(1 <= MOD, format("MOD must satisfy 1 <= MOD. Now MOD =  %s.", MOD));
    assert(MOD <= int.max, format("MOD must satisfy MOD*MOD <= long.max. Now MOD = %s.", MOD));
}
do {
    return mod_pow(x, MOD-2, MOD);
}

// check mod_inv
static assert(__traits(compiles, mod_inv(998244353, 1_000_000_007)));

class PrimeModuloFactorial (ulong M)
{
    /// methods:
    /// - void build (ulong N_)
    /// - long binom (ulong n_, ulong k_)
    /// - long factorial (ulong x_)
    /// - long factorial_inv (ulong x_)

    import std.conv : to;
    import std.format : format;

    // varidate
    static assert(1 <= M && M < int.max, format("PrimeModuloFactorial: M = %s is out of range. M must be in range of [1, %s].", M, int.max));

    private static bool internal_is_prime (int x) {
        if (x <= 1) return false;
        foreach (i; 2..x + 1) {
            if (x < 1L * i * i) break;
            if (x % i == 0) return false;
        }
        return true;
    }
    static assert(internal_is_prime(M.to!int), format("PrimeModuloFactorial: M = %s is not prime number.", M));

    private:
        static long[] fact, fact_inv;
        static int N = 0;
        static long MOD = M;

    public:
        @disable this () {}

        static void build (ulong N_)
        in {
            assert(0 <= N_ && N_ <= 10^^8, format("N = %s does not satisfy constraints. N must be in range of [0, 10^8].", N_));
        }
        do {
            if (N_ <= N) { N = N_.to!int; return; }
            N = N_.to!int;
            fact.length = fact_inv.length = N + 1;

            fact[0] = 1;
            for (int i = 1; i <= N; i++) fact[i] = i * fact[i - 1] % MOD;
            fact_inv[N] = mod_inv(fact[N], MOD);
            for (int i = N; 0 < i; i--) fact_inv[i - 1] = i * fact_inv[i] % MOD;
        }

        static long binom (ulong n_, ulong k_)
        in {
            assert((n_ < k_
                    || (n_ <= N && k_ <= N)),
                    format("Out of range of pre-calculation. MAX = %s, n = %s, k = %s.", N, n_, k_),
                    );
        }
        do {
            int n = n_.to!int;
            int k = k_.to!int;

            if (n < k) return 0;
            long res = fact[n] * fact_inv[k] % MOD;
            return res * fact_inv[n - k] % MOD;
        }

        static long factorial (ulong x_)
        in {
            assert(x_ <= N,
                    format("Out of range of pre-calculation. MAX = %s, x = %s.", N, x_),
                    );
        }
        do {
            int x = x_.to!int;
            return fact[x];
        }

        static long factorial_inv (ulong x_)
        in {
            assert(x_ <= N,
                    format("Out of range of pre-calculation. MAX = %s, x = %s.", N, x_)
                    );
        }
        do {
            int x = x_.to!int;
            return fact_inv[x];
        }
}

import std.typecons : Tuple, tuple;

class LinearSieve {
    /// methods
    /// - void build (ulong N_)
    /// - Tuple!(long, long)[] prime_factors (ulong N_)
    /// - bool is_prime (ulong N_)
    /// - long[] divisors (ulong N_)

    private:
        static int N = 0;
        static int[] lpf;
        static int[] primes;
        static int[] lpf_ord;
        static int[] lpf_pow;

    import std.conv : to;
    import std.format : format;

    public:
        @disable this () {}

        static void build (ulong N_)
        in {
            assert(2 <= N_ && N_ <= int.max, format("Argument N_ = %s does not meet condition.", N_));
        }
        do {
            // Linear sieve.
            if (N+1 <= lpf.length) return;
            N = N_.to!int;

            primes.length = 0;
            lpf.length = N+1;

            lpf[0] = lpf[1] = 1;

            for (int i = 2; i <= N; i++) {
                if (lpf[i] == 0) {
                    lpf[i] = i;
                    primes ~= i;
                }

                foreach (p; primes) {
                    if (lpf[i] < p) break;
                    if (N < 1L * i * p) break;
                    lpf[i * p] = p;
                }
            }

            // Precomputation of prime factorization.
            lpf_ord.length = lpf_pow.length = N+1;
            lpf_pow[] = 1;

            for (int i = 2; i <= N; i++) {
                int prev = i / lpf[i];

                if (lpf[i] == lpf[prev]) {
                    lpf_ord[i] = lpf_ord[prev] + 1;
                    lpf_pow[i] = lpf_pow[prev] * lpf[i];
                }
                else {
                    lpf_ord[i] = 1;
                    lpf_pow[i] = lpf[i];
                }
            }
        }

        static Tuple!(long, long)[] prime_factors (ulong N_)
        in {
            assert(2 <= N_ && N_ <= N, format("Argument N_ = %s is not out of range. The valid range is [2, %s].", N_, N));
        }
        do {
            int n = N_.to!int;
            Tuple!(long, long)[] res;

            while (1 < n) {
                res ~= tuple(1L*lpf[n], 1L*lpf_ord[n]);
                n /= lpf_pow[n];
            }

            return res;
        }

        static bool is_prime (ulong N_)
        in {
            assert(2 <= N_ && N_ <= N, format("Argument N_ = %s is not out of range. The valid range is [2, %s].", N_, N));
        }
        do {
            int N = N_.to!int;
            return lpf[N] == N;
        }

        static long[] divisors (ulong N_)
        in {
            assert(N_ <= N, format("Argument N_ = %s is not out of range. The valid range is [2, %s].", N_, N));
        }
        do {
            if (N_ == 1) return [1L];

            import std.container : SList;
            import std.algorithm : sort;

            auto fac = prime_factors(N_);

            static SList!(Tuple!(int, long)) Q;
            Q.insertFront(tuple(0, 1L)); // (処理済み階層, 値)

            long[] res;
            while (!Q.empty) {
                auto h = Q.front; Q.removeFront;
                if (h[0] == fac.length) {
                    res ~= h[1];
                    continue;
                }

                auto p = fac[h[0]];
                long prod = 1;
                foreach (i; 0..p[1] + 1) {
                    Q.insertFront(tuple(h[0] + 1, h[1] * prod));
                    prod *= p[0];
                }
            }

            res.sort;
            return res;
        }
}
0