結果
問題 | No.811 約数の個数の最大化 |
ユーザー |
![]() |
提出日時 | 2020-08-19 18:12:01 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 203 ms / 2,000 ms |
コード長 | 1,899 bytes |
コンパイル時間 | 209 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 77,184 KB |
最終ジャッジ日時 | 2024-10-12 05:07:39 |
合計ジャッジ時間 | 2,908 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
# import sys; input = sys.stdin.buffer.readline# sys.setrecursionlimit(10**7)from collections import defaultdictcon = 10 ** 9 + 7; INF = float("inf")def getlist():return list(map(int, input().split()))def gcd(a, b):while b:a, b = b, a % breturn adef isPrimeMR(N):d = N - 1d = d // (d & -d)# L=[2,3,61]L = [2]for a in L:t = dy = pow(a, t, N)if y == 1:continuewhile y != N - 1:y = (y * y) % Nif y == 1 or t == N - 1:return 0return 1def findFactorRho(N):m = 1 << N.bit_length() // 8for c in range(1, 99):f = lambda x: (x * x + c) % Ny, r, q, g = 2, 1, 1, 1while g == 1:x = yfor i in range(r):y = f(y)k = 0while k < r and g == 1:ys = yfor i in range(min(m, r - k)):y = f(y)q = q * abs(x - y) % Ng = gcd(q, N)k += mr <<= 1if g == N:g = 1while g == 1:ys = f(ys)g = gcd(abs(x - ys), N)if g < N:if isPrimeMR(g):return gelif isPrimeMR(N // g):return N // greturn findFactorRho(g)def primeFactor(N):i = 2ret = defaultdict(int)rhoFlg = 0while i * i <= N:k = 0while N % i == 0:N //= ik += 1if k:ret[i] = ki += 1 + i % 2if i == 101 and N >= 2 ** 20:while N > 1:if isPrimeMR(N):ret[N], N = 1, 1else:rhoFlg = 1j = findFactorRho(N)k = 0while N % j == 0:N //= jk += 1ret[j] = kif N > 1:ret[N] = 1if rhoFlg:ret = {x: ret[x] for x in sorted(ret)}return ret#処理内容def main():N, K = getlist()D = primeFactor(N)ans = INFval = 0for i in range(N - 1, 0, -1):d = primeFactor(i)fac_cnt = 0for j in d:fac_cnt += min(d[j], D[j])if fac_cnt >= K:divnum = 1for j in d:divnum *= d[j] + 1if divnum >= val:ans = ival = divnumprint(ans)if __name__ == '__main__':main()