結果
問題 |
No.1711 Divide LCM
|
ユーザー |
|
提出日時 | 2021-08-05 22:05:38 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,402 bytes |
コンパイル時間 | 238 ms |
コンパイル使用メモリ | 82,320 KB |
実行使用メモリ | 100,172 KB |
最終ジャッジ日時 | 2024-09-17 16:58:36 |
合計ジャッジ時間 | 17,986 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 2 |
other | AC * 5 WA * 37 |
ソースコード
M = 10**6 spf = [i for i in range(M+1)] for i in range(2,M+1): if spf[i]==i: for j in range(2*i,M+1,i): spf[j] = i def factorization(n): assert 1<=n<=10**6 res = {} while n!=1: p = spf[n] res[p] = 0 while n%p==0: res[p] += 1 n //= p return res from collections import deque N = int(input()) A = list(map(int,input().split())) pre = [0 for i in range(M+1)] cnt = [0 for i in range(M+1)] for a in A: prime = factorization(a) for p in prime: pre[p] = max(pre[p],pow(p,prime[p])) cnt[a] += 1 P = [val for val in pre if val!=0] for i in range(1,M+1): for j in range(2*i,M+1,i): cnt[i] += cnt[j] n = len(P) deq = deque([(1,-1)]) break_point = -1 while deq: v,k = deq.popleft() for i in range(k+1,n): if M < v * P[i]: break_point = v * P[i] deq = [] break if not cnt[v*P[i]]: break_point = v * P[i] deq = [] break deq.append((v*P[i],i)) if break_point==-1: exit(print(-1)) k = 0 p = [] for i in range(n): if break_point%P[i]==0: p.append(P[i]) k += 1 S = [[] for i in range(k)] for a in A: for i in range(k): if a%p[i]: S[i].append(a) break print(k) for i in range(k): S[i] = [len(S[i])] + S[i] print(*S[i])