結果
問題 | No.2896 Monotonic Prime Factors |
ユーザー |
👑 |
提出日時 | 2024-09-12 16:35:40 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 774 bytes |
コンパイル時間 | 478 ms |
コンパイル使用メモリ | 82,324 KB |
実行使用メモリ | 200,324 KB |
最終ジャッジ日時 | 2024-09-12 16:35:51 |
合計ジャッジ時間 | 10,355 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 16 RE * 2 |
ソースコード
# 異常系(階乗全列挙不足)P = 998244353# 階乗factorial = [1]for i in range(1, 16 * 10**5 - 1):factorial.append(factorial[-1] * i % P)# 二項係数def comb(n, r):if n < r:return 0return factorial[n] * pow(factorial[r], P - 2, P) % P * pow(factorial[n - r], P - 2, P) % P# 素因数の個数def count_prime(n):count = 0while n % 2 == 0:n //= 2count += 1p = 3while p**2 <= n:if n % p == 0:n //= pcount += 1else:p += 2if n > 1:count += 1return count# solveQ = int(input())count = 0for _ in range(Q):A, B = map(int, input().split())count += count_prime(A)print(comb(count - 1, B - 1))