結果
問題 |
No.811 約数の個数の最大化
|
ユーザー |
![]() |
提出日時 | 2019-04-15 16:57:11 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 660 ms / 2,000 ms |
コード長 | 799 bytes |
コンパイル時間 | 236 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 12,544 KB |
最終ジャッジ日時 | 2024-09-22 07:59:40 |
合計ジャッジ時間 | 3,030 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
import math, collections, functools @functools.lru_cache() def prime_division(x): primes = [] for i in range(2, math.ceil(math.sqrt(x)) + 1): while x % i == 0: primes.append(i) x //= i if x > 1: primes.append(x) return primes @functools.lru_cache() def count_factor(x): ans = 1 for v in collections.Counter(prime_division(x)).values(): ans *= v + 1 return ans @functools.lru_cache() def gcd(a, b): # a < b while b % a != 0: a, b = b % a, a return a if __name__ == '__main__': n, k = map(int, input().split()) d = collections.defaultdict(list) for m in range(2, n): if len(prime_division(gcd(m, n))) >= k: d[count_factor(m)].append(m) print(min(d[max(d)]))