結果
問題 |
No.2497 GCD of LCMs
|
ユーザー |
![]() |
提出日時 | 2023-10-06 23:06:47 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,718 bytes |
コンパイル時間 | 322 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 630,728 KB |
最終ジャッジ日時 | 2024-07-26 16:55:34 |
合計ジャッジ時間 | 4,495 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 1 MLE * 1 |
other | WA * 3 MLE * 1 -- * 10 |
ソースコード
import sys input = sys.stdin.readline sys.setrecursionlimit(500000) mod=998244353 n,m=map(int,input().split()) a=list(map(int,input().split())) def Eratosthenes(N): #N以下の素数のリストを返す N+=1 is_prime_list = [True]*N m = int(N**0.5)+1 for i in range(3,m,2): if is_prime_list[i]: is_prime_list[i*i::2*i]=[False]*((N-i*i-1)//(2*i)+1) return [2] + [i for i in range(3,N,2) if is_prime_list[i]] e=Eratosthenes(10**6) from collections import defaultdict def factorization(n): global e arr = defaultdict(int) temp = n sqrtn=int(-(-n**0.5//1))+1 for i in e: if i<=sqrtn: if temp%i==0: cnt=0 while temp%i==0: cnt+=1 temp //= i arr[i]=cnt else: break if temp!=1: arr[temp]=1 if arr==[]: if n!=1: arr[n]=1 return arr A=[] for i in range(n): A.append(factorization(a[i])) adj = [[] for _ in range(n)] for _ in range(m): u,v = map(int, input().split()) adj[u-1].append(v-1) adj[v-1].append(u-1) seen = [0]*n from collections import defaultdict memo=[[] for _ in range(n)] def dfs(pa,v): global dic,memo seen[v]=1 for i in A[v]: dic[i]=max(dic[i],A[v][i]) dic2=defaultdict(int) for i in dic: dic2[i]=dic[i] memo[v].append(dic2) for w in adj[v]: if seen[w]==0: dfs(v,w) seen[v]=0 if pa>-1: dic=defaultdict(int) v=memo[pa][-1] for i in v: dic[i]=v[i] dic=defaultdict(int) dfs(-1,0) for i in range(n): dic=memo[i][0] for d in memo[i]: for j in d: dic[j]=min(dic[j],d[j]) ans=1 for i in dic: ans*=pow(i,dic[i],mod) ans%=mod print(ans)