結果
問題 | No.811 約数の個数の最大化 |
ユーザー |
|
提出日時 | 2020-04-22 13:36:33 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 756 ms / 2,000 ms |
コード長 | 1,129 bytes |
コンパイル時間 | 85 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 10,880 KB |
最終ジャッジ日時 | 2024-10-11 07:07:03 |
合計ジャッジ時間 | 5,092 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
def sieve(n):primes = [1 if i%2 == 1 else 0 for i in range(n + 1)]primes[1] = 0primes[2] = 1for i in range(3,n + 1,2):if i * i > n:breakif primes[i]:for j in range(i * i,n + 1,i):primes[j] = 0return [p for p in range(2,n + 1) if primes[p] == 1]def Factor(n,k,primes,fact):ans = 1common_prime = 0for p in primes:cnt = 1while n%p == 0:n //= pcnt += 1ans *= cntif p in fact:common_prime += min(cnt - 1,fact[p])if n!= 1:ans *= 2if n in fact:common_prime += 1if common_prime >= k:return anselse:return -1n,k = map(int,input().split())primes = sieve(int(n ** 0.5) + 3)fact = {}m = nfor p in primes:while n%p == 0:n //= pif p in fact:fact[p] += 1else:fact[p] = 1if n != 1:fact[n] = 1ans = 10 ** 9cnt = 0for i in range(1,m):ret = Factor(i,k,primes,fact)if cnt < ret:ans = icnt = retprint(ans)