結果
問題 | No.811 約数の個数の最大化 |
ユーザー |
|
提出日時 | 2020-06-09 12:22:49 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 222 ms / 2,000 ms |
コード長 | 905 bytes |
コンパイル時間 | 508 ms |
コンパイル使用メモリ | 82,504 KB |
実行使用メモリ | 78,012 KB |
最終ジャッジ日時 | 2024-12-31 15:04:21 |
合計ジャッジ時間 | 2,817 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
from math import gcddef factors(n):f = []c = 0while n % 2 == 0:n //= 2c += 1if c > 0:f.append([2, c])p = 3while p * p <= n:if n % p == 0:c = 0while n % p == 0:n //= pc += 1if c > 0:f.append([p, c])p += 2if n != 1:f.append([n, 1])return fdef divisors(n):divs = []for d in range(1, int(n**0.5) + 1):if n % d == 0:divs.append(d)q = n // dif q != d:divs.append(q)return divsN, K = map(int, input().split())ans = 0max_ndivs = 0for i in range(2, N):g = gcd(i, N)k = sum(f[1] for f in factors(g))if k < K: continuendivs = len(divisors(i))if ndivs > max_ndivs:max_ndivs = ndivsans = iprint(ans)