結果
問題 | No.811 約数の個数の最大化 |
ユーザー |
|
提出日時 | 2022-07-04 20:09:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 538 ms / 2,000 ms |
コード長 | 4,470 bytes |
コンパイル時間 | 291 ms |
コンパイル使用メモリ | 82,352 KB |
実行使用メモリ | 96,544 KB |
最終ジャッジ日時 | 2024-12-14 12:43:38 |
合計ジャッジ時間 | 6,423 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
###素因数分解###def prime_factorize(n: int) -> list:return_list = []while n % 2 == 0:return_list.append(2)n //= 2f = 3while f * f <= n:if n % f == 0:return_list.append(f)n //= felse:f += 2if n != 1:return_list.append(n)return return_list###ある数が素数かどうかの判定###import mathdef is_prime(n):sqrt_n = math.ceil(math.sqrt(n))for i in range(2, sqrt_n):if n % i == 0:return Falsereturn True###N以下の素数列挙###import mathdef sieve_of_eratosthenes(n):prime = [True for i in range(n+1)]prime[0] = Falseprime[1] = Falsesqrt_n = math.ceil(math.sqrt(n))for i in range(2, sqrt_n+1):if prime[i]:for j in range(2*i, n+1, i):prime[j] = Falsereturn prime###N以上K以下の素数列挙###import mathdef segment_sieve(a, b):sqrt_b = math.ceil(math.sqrt(b))prime_small = [True for i in range(sqrt_b)]prime = [True for i in range(b-a+1)]for i in range(2, sqrt_b):if prime_small[i]:for j in range(2*i, sqrt_b, i):prime_small[j] = Falsefor j in range((a+i-1)//i*i, b+1, i):#print('j: ', j)prime[j-a] = Falsereturn prime###n進数から10進数変換###def base_10(num_n,n):num_10 = 0for s in str(num_n):num_10 *= nnum_10 += int(s)return num_10###10進数からn進数変換###def base_n(num_10,n):str_n = ''while num_10:if num_10%n>=10:return -1str_n += str(num_10%n)num_10 //= nreturn int(str_n[::-1])###複数の数の最大公約数、最小公倍数###from functools import reduce# 最大公約数def gcd_list(num_list: list) -> int:return reduce(gcd, num_list)# 最小公倍数def lcm_base(x: int, y: int) -> int:return (x * y) // gcd(x, y)def lcm_list(num_list: list):return reduce(lcm_base, num_list, 1)###約数列挙###def make_divisors(n):lower_divisors, upper_divisors = [], []i = 1while i * i <= n:if n % i == 0:lower_divisors.append(i)if i != n // i:upper_divisors.append(n//i)i += 1return lower_divisors + upper_divisors[::-1]###順列###def nPr(n, r):npr = 1for i in range(n, n-r, -1):npr *= ireturn npr###組合せ###def nCr(n, r):factr = 1r = min(r, n - r)for i in range(r, 1, -1):factr *= ireturn nPr(n, r)/factrimport sys, refrom math import ceil, floor, sqrt, pi, factorial, gcdfrom copy import deepcopyfrom collections import Counter, deque, defaultdictfrom heapq import heapify, heappop, heappushfrom itertools import accumulate, product, combinations, combinations_with_replacement, permutationsfrom bisect import bisect, bisect_left, bisect_rightfrom functools import reducefrom decimal import Decimal, getcontextdef i_input(): return int(input())def i_map(): return map(int, input().split())def i_list(): return list(i_map())def i_row(N): return [i_input() for _ in range(N)]def i_row_list(N): return [i_list() for _ in range(N)]def s_input(): return input()def s_map(): return input().split()def s_list(): return list(s_map())def s_row(N): return [s_input for _ in range(N)]def s_row_str(N): return [s_list() for _ in range(N)]def s_row_list(N): return [list(s_input()) for _ in range(N)]def lcm(a, b): return a * b // gcd(a, b)def get_distance(x1, y1, x2, y2):d = sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)return ddef rotate(table):n_fild = []for x in zip(*table[::-1]):n_fild.append(x)return n_fildsys.setrecursionlimit(10 ** 7)INF = float('inf')MOD = 10 ** 9 + 7MOD2 = 998244353def main():n, k = i_map()nums = prime_factorize(n)count = Counter(nums)ans = INFbase = 0for i in range(n-1, 0, -1):lines = prime_factorize(i)score = 0new_nums = deepcopy(count)for j in range(len(lines)):if new_nums[lines[j]] > 0:score += 1new_nums[lines[j]] -= 1if score >= k:total = 1cou_line = Counter(lines)for key, value in cou_line.items():total *= (value+1)base = max(base, total)if base == total:ans = min(ans, i)print(ans)if __name__ == '__main__':main()