結果

問題 No.811 約数の個数の最大化
ユーザー rookzenorookzeno
提出日時 2019-04-12 21:40:12
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 305 ms / 2,000 ms
コード長 1,675 bytes
コンパイル時間 313 ms
コンパイル使用メモリ 87,232 KB
実行使用メモリ 80,128 KB
最終ジャッジ日時 2023-10-12 19:19:34
合計ジャッジ時間 4,250 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 93 ms
71,680 KB
testcase_01 AC 129 ms
77,648 KB
testcase_02 AC 292 ms
79,500 KB
testcase_03 AC 94 ms
71,504 KB
testcase_04 AC 102 ms
76,340 KB
testcase_05 AC 149 ms
78,712 KB
testcase_06 AC 192 ms
79,256 KB
testcase_07 AC 190 ms
78,672 KB
testcase_08 AC 247 ms
79,532 KB
testcase_09 AC 247 ms
80,128 KB
testcase_10 AC 196 ms
78,644 KB
testcase_11 AC 267 ms
79,756 KB
testcase_12 AC 198 ms
78,768 KB
testcase_13 AC 280 ms
79,620 KB
testcase_14 AC 305 ms
79,880 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
n,k = map(int,input().split())
import math
def factorization(n):
    def factor_sub(n, m):
        c = 0
        while n % m == 0:
            c += 1
            n //= m
        return c, n
    #
    buff = []
    c, m = factor_sub(n, 2)
    if c > 0: buff.append((2, c))
    c, m = factor_sub(m, 3)
    if c > 0: buff.append((3, c))
    x = 5
    while m >= x * x:
        c, m = factor_sub(m, x)
        if c > 0: buff.append((x, c))
        if x % 6 == 5:
            x += 2
        else:
            x += 4
    if m > 1: buff.append((m, 1))
    return buff
#a = factorization(n)
#b = []
#for i,j in a:
#  b.append(i)
def divisor_sub(p, q):
    a = []
    for i in range(0, q + 1):
        a.append(p ** i)
    return a

def divisor(n):
    if n == 1:
      return([1])
    xs = factorization(n)
    ys = divisor_sub(xs[0][0], xs[0][1])
    for p, q in xs[1:]:
        ys = [x * y for x in divisor_sub(p, q) for y in ys]
    return sorted(ys)
#素因数列挙
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n //= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(n)
  table = set(table)
  table = list(table)
  return table

x = factorization(n)
d = defaultdict(int)
for i in range(len(x)):
    d[x[i][0]] = x[i][1]
ans = 0
res = -1
#print(d)
for i in range(2,n):
    a = factorization(i)
    tmp = 0
    tmp2 = 1
    for j in range(len(a)):
        tmp += min(a[j][1],d[a[j][0]])
        tmp2 *= (a[j][1]+1)
    if k <= tmp:
        if ans < tmp2:
            ans = tmp2
            res = i
print(res)
0