結果
問題 | No.2718 Best Consonance |
ユーザー |
|
提出日時 | 2024-04-06 14:41:40 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,137 ms / 4,000 ms |
コード長 | 1,795 bytes |
コンパイル時間 | 440 ms |
コンパイル使用メモリ | 82,136 KB |
実行使用メモリ | 150,536 KB |
最終ジャッジ日時 | 2024-10-02 13:00:15 |
合計ジャッジ時間 | 33,137 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 36 |
ソースコード
import syssys.setrecursionlimit(5*10**5)input = sys.stdin.readlinefrom collections import defaultdict, deque, Counterfrom heapq import heappop, heappushfrom bisect import bisect_left, bisect_rightfrom math import gcdclass Era:def __init__(self, n):self.N = nself.l = [i for i in range(n+1)]for i in range(2,min(n,n//2+10)):if self.l[i] == i:for p in range(i+i,n+1,i):if self.l[p] == p:self.l[p] = i# 素数判定def isprime(self,n):return self.l[n] == n# 素因数分解def primes(self,n):ans = []now = nwhile now != 1:if not ans:ans.append([self.l[now], 1])else:if ans[-1][0] == self.l[now]:ans[-1][1] += 1else:ans.append([self.l[now], 1])now //= self.l[now]return ans# 約数列挙def facts(self,n):pf = self.primes(n)ans = [1]for pn, cnt in pf:tmp = [pow(pn, i) for i in range(1, cnt+1)]m = len(ans)for num in tmp:for i in range(m):ans.append(ans[i]*num)return ansera = Era(202020)n = int(input())ab = []cs = []for i in range(n):a,b= map(int,input().split())c = a*bcs.append((c,i))ab.append([a,b])cs.sort()cs = cs[::-1]d = defaultdict(lambda :10**10)ans = 0for ci, i in cs:ai,bi = ab[i]fs = era.facts(ai)tmp = 0for num in fs:if d[num] == 10**10: continuetmp = max(tmp, bi*num//d[num])for num in fs:d[num] = min(d[num], ai)ans = max(tmp, ans)print(ans)