結果
問題 |
No.811 約数の個数の最大化
|
ユーザー |
![]() |
提出日時 | 2019-12-19 20:25:51 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 401 ms / 2,000 ms |
コード長 | 800 bytes |
コンパイル時間 | 212 ms |
コンパイル使用メモリ | 12,416 KB |
実行使用メモリ | 10,752 KB |
最終ジャッジ日時 | 2024-07-07 01:37:03 |
合計ジャッジ時間 | 1,899 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
import math def count_prime_factor(N): if N == 1: return 0 ret = 0 tmp = N c = int(math.sqrt(N)) + 1 for n in range(2, c): while tmp % n == 0: tmp = tmp // n ret += 1 if tmp == 1: break if tmp != 1: ret += 1 if ret: return ret else: return 1 def count_divisor(N): ret = 0 c = int(math.sqrt(N))+1 for i in range(1, c): if N % i == 0: ret += 1 if N != i * i: ret += 1 return ret N, K = map(int, input().split()) max_d = 0 ans = 0 for n in range(1, N): gcd = math.gcd(N, n) if count_prime_factor(gcd) >= K: d = count_divisor(n) if max_d < d: max_d = d ans = n print(ans)