結果
問題 | No.1058 素敵な数 |
ユーザー |
![]() |
提出日時 | 2023-06-09 07:03:00 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 61 ms / 2,000 ms |
コード長 | 2,551 bytes |
コンパイル時間 | 208 ms |
コンパイル使用メモリ | 12,928 KB |
実行使用メモリ | 12,544 KB |
最終ジャッジ日時 | 2024-12-31 13:54:14 |
合計ジャッジ時間 | 1,368 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 9 |
ソースコード
import sysreadline=sys.stdin.readlineclass 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 -1Pr=Prime(10**5+1000)primes=[p for p in Pr.primes if p>10**5]le=len(primes)lst=[1]+[primes[i]*primes[j] for i in range(le) for j in range(i,le)]lst.sort()N=int(readline())ans=lst[N-1]print(ans)