結果
| 問題 |
No.2896 Monotonic Prime Factors
|
| コンテスト | |
| ユーザー |
 InTheBloom
|
| 提出日時 | 2024-09-20 22:56:58 |
| 言語 | D (dmd 2.109.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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 18 |
ソースコード
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;
}
}