結果
問題 | 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 sys from collections import deque input = 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] *= t D = [d for d in D] + [d*t for d in D] if p in LCM: LCM[p] = max(LCM[p],t) else: LCM[p] = t for d in D: all_divisors.add(d) prime_pow = [LCM[p] for p in LCM] n = len(prime_pow) deq = deque([(1,-1)]) prod = -1 while 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 = [] break deq.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) break print(k) for i in range(k): S[i] = [len(S[i])] + S[i] print(*S[i])