結果
問題 |
No.1809 Divide NCK
|
ユーザー |
![]() |
提出日時 | 2025-03-20 18:58:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 51 ms / 2,000 ms |
コード長 | 677 bytes |
コンパイル時間 | 155 ms |
コンパイル使用メモリ | 82,292 KB |
実行使用メモリ | 59,160 KB |
最終ジャッジ日時 | 2025-03-20 18:59:56 |
合計ジャッジ時間 | 2,997 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 |
ソースコード
def count_p_in_factorial(n, p): count = 0 while n > 0: n = n // p count += n return count N, K, M = map(int, input().split()) # Factorize M factors = {} m = M i = 2 while i * i <= m: while m % i == 0: factors[i] = factors.get(i, 0) + 1 m = m // i i += 1 if m > 1: factors[m] = 1 min_x = float('inf') for p, e in factors.items(): cnt_n = count_p_in_factorial(N, p) cnt_k = count_p_in_factorial(K, p) nk = N - K cnt_nk = count_p_in_factorial(nk, p) if nk != 0 else 0 v_p = cnt_n - cnt_k - cnt_nk x_p = v_p // e if x_p < min_x: min_x = x_p ans = min_x if min_x >= 0 else 0 print(ans)