結果
問題 | No.1711 Divide LCM |
ユーザー |
|
提出日時 | 2021-08-06 21:14:33 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,562 bytes |
コンパイル時間 | 435 ms |
コンパイル使用メモリ | 82,108 KB |
実行使用メモリ | 61,712 KB |
最終ジャッジ日時 | 2024-09-17 16:59:12 |
合計ジャッジ時間 | 10,304 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 2 |
other | AC * 5 WA * 37 |
ソースコード
M = 10**3 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 prime = [i for i in range(2,M+1) if spf[i]==i] def factorization(n): assert 1<=n<=10**6 res = {} for p in prime: cnt = 0 while n%p==0: cnt += 1 n //= p if cnt: res[p] = cnt if n!=1: res[n] = 1 return res def divisors(M): d=[] i=1 while M>=i**2: if M%i==0: d.append(i) if i**2!=M: d.append(M//i) i=i+1 return d from collections import deque N = int(input()) A = list(map(int,input().split())) pre = [0 for i in range(M+1)] all_divisors = set() for a in A: a_prime = factorization(a) for p in a_prime: pre[p] = max(pre[p],pow(p,a_prime[p])) div = divisors(a) for d in div: all_divisors.add(d) P = [val for val in pre if val!=0] n = len(P) deq = deque([(1,-1)]) break_point = -1 while deq: v,k = deq.popleft() for i in range(k+1,n): if not v*P[i] in all_divisors: 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])