結果
問題 | No.1711 Divide LCM |
ユーザー |
|
提出日時 | 2021-08-13 04:05:16 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 596 ms / 4,000 ms |
コード長 | 1,223 bytes |
コンパイル時間 | 245 ms |
コンパイル使用メモリ | 82,700 KB |
実行使用メモリ | 188,184 KB |
最終ジャッジ日時 | 2024-09-17 17:01:41 |
合計ジャッジ時間 | 14,461 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
import sysfrom collections import dequeinput = lambda :sys.stdin.readline().rstrip()mi = lambda :map(int,input().split())li = lambda :list(mi())N = int(input())LCM = {}all_divisors = set()A = [1 for i in range(N)]for i in range(N):m = int(input())D = [1]for _ in range(m):p,e = mi()t = pow(p,e)A[i] *= tD = [d for d in D] + [d*t for d in D]if p in LCM:LCM[p] = max(LCM[p],t)else:LCM[p] = tfor d in D:all_divisors.add(d)prime_pow = [LCM[p] for p in LCM]n = len(prime_pow)deq = deque([(1,-1)])prod = -1while deq:v,k = deq.popleft()for i in range(k+1,n):if v * prime_pow[i] not in all_divisors:prod = v * prime_pow[i]deq = []breakdeq.append((v*prime_pow[i],i))if prod==-1:exit(print(-1))selected_p = []for i in range(n):if prod%prime_pow[i]==0:selected_p.append(prime_pow[i])k = len(selected_p)S = [[] for i in range(k)]for a in A:for i in range(k):if a%selected_p[i]:S[i].append(a)breakprint(k)for i in range(k):S[i] = [len(S[i])] + S[i]print(*S[i])