結果
問題 | No.2896 Monotonic Prime Factors |
ユーザー |
👑 |
提出日時 | 2024-09-12 16:04:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 880 ms / 2,000 ms |
コード長 | 730 bytes |
コンパイル時間 | 406 ms |
コンパイル使用メモリ | 81,976 KB |
実行使用メモリ | 199,296 KB |
最終ジャッジ日時 | 2024-09-12 16:04:35 |
合計ジャッジ時間 | 10,452 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
P = 998244353# 階乗factorial = [1]for i in range(1, 16 * 10**5):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))