結果

問題 No.811 約数の個数の最大化
コンテスト
ユーザー rookzeno
提出日時 2019-04-12 21:40:12
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 248 ms / 2,000 ms
コード長 1,675 bytes
コンパイル時間 272 ms
コンパイル使用メモリ 82,144 KB
実行使用メモリ 78,592 KB
最終ジャッジ日時 2024-09-14 17:43:27
合計ジャッジ時間 3,150 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

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