結果
問題 | No.811 約数の個数の最大化 |
ユーザー |
![]() |
提出日時 | 2022-09-22 05:29:37 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 142 ms / 2,000 ms |
コード長 | 3,670 bytes |
コンパイル時間 | 172 ms |
コンパイル使用メモリ | 13,184 KB |
実行使用メモリ | 15,036 KB |
最終ジャッジ日時 | 2024-12-22 04:40:24 |
合計ジャッジ時間 | 2,176 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
import bisectimport copyimport decimalimport fractionsimport heapqimport itertoolsimport mathimport randomimport sysimport timefrom collections import Counter,deque,defaultdictfrom functools import lru_cache,reducefrom heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_maxdef _heappush_max(heap,item):heap.append(item)heapq._siftdown_max(heap, 0, len(heap)-1)def _heappushpop_max(heap, item):if heap and item < heap[0]:item, heap[0] = heap[0], itemheapq._siftup_max(heap, 0)return itemfrom math import gcd as GCDread=sys.stdin.readreadline=sys.stdin.readlinereadlines=sys.stdin.readlineswrite=sys.stdout.writeclass Prime:def __init__(self,N):assert N<=10**8self.smallest_prime_factor=[None]*(N+1)for i in range(2,N+1,2):self.smallest_prime_factor[i]=2n=int(N**.5)+1for p in range(3,n,2):if self.smallest_prime_factor[p]==None:self.smallest_prime_factor[p]=pfor i in range(p**2,N+1,2*p):if self.smallest_prime_factor[i]==None:self.smallest_prime_factor[i]=pfor p in range(n,N+1):if self.smallest_prime_factor[p]==None:self.smallest_prime_factor[p]=pself.primes=[p for p in range(N+1) if p==self.smallest_prime_factor[p]]def Factorize(self,N):assert N>=1factors=defaultdict(int)if N<=len(self.smallest_prime_factor)-1:while N!=1:factors[self.smallest_prime_factor[N]]+=1N//=self.smallest_prime_factor[N]else:for p in self.primes:while N%p==0:N//=pfactors[p]+=1if N<p*p:if N!=1:factors[N]+=1breakif N<=len(self.smallest_prime_factor)-1:while N!=1:factors[self.smallest_prime_factor[N]]+=1N//=self.smallest_prime_factor[N]breakelse:if N!=1:factors[N]+=1return factorsdef Divisors(self,N):assert N>0divisors=[1]for p,e in self.Factorize(N).items():pow_p=[1]for _ in range(e):pow_p.append(pow_p[-1]*p)divisors=[i*j for i in divisors for j in pow_p]return divisorsdef Is_Prime(self,N):return N==self.smallest_prime_factor[N]def Totient(self,N):for p in self.Factorize(N).keys():N*=p-1N//=preturn Ndef Mebius(self,N):fact=self.Factorize(N)for e in fact.values():if e>=2:return 0else:if len(fact)%2==0:return 1else:return -1def Divisor_Counts(N):divisor_counts=[float('inf')]+[1]*Nfor p in range(2,N+1):if divisor_counts[p]!=1:continuepp=pe=1while pp<=N:for i in range(pp,N+1,pp):divisor_counts[i]+=divisor_counts[i]//ee+=1pp*=preturn divisor_countsN,K=map(int,readline().split())P=Prime(N)DC=Divisor_Counts(N)cnt=[0]*(N+1)for p,e in P.Factorize(N).items():for i in range(1,e+1):for n in range(p**i,N+1,p**i):cnt[n]+=1m=max(DC[M] for M in range(1,N) if cnt[M]>=K)for M in range(1,N):if cnt[M]>=K and DC[M]==m:breakprint(M)