結果
問題 | No.2519 Coins in Array |
ユーザー |
![]() |
提出日時 | 2023-10-27 23:26:14 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 414 ms / 2,000 ms |
コード長 | 1,663 bytes |
コンパイル時間 | 785 ms |
コンパイル使用メモリ | 82,128 KB |
実行使用メモリ | 151,312 KB |
最終ジャッジ日時 | 2024-09-25 15:23:40 |
合計ジャッジ時間 | 9,973 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 37 |
ソースコード
import mathclass Sieve_of_Eratosthenes:def __init__(self, n):self.n = nself.p_list=[]self.minp = [0] * (n + 1)for i in range(2, n + 1):if self.minp[i] == 0:self.p_list.append(i)self.minp[i] = ifor j in range(i * i, n + 1, i):if self.minp[j] == 0:self.minp[j] = idef prime_factorization(self, n):factors = {}prev_p = -1while n > 1:p = self.minp[n]if p != prev_p:factors[p] = 1prev_p = pelse:factors[p] += 1n //= preturn factorsera=Sieve_of_Eratosthenes(2*10**5)N=int(input())A=list(map(int,input().split()))dics=[era.prime_factorization(A[i]) for i in range(N)]#print(dics)flag=[-1 for i in range(2*10**5)]for i in range(N):for j in dics[i].keys():if flag[j]==-1:flag[j]=ielse:print(0)print(flag[j]+1,i+1)for i in range(N-2):print(1,N-1-i)exit()def f(x,y):if math.gcd(x,y)==1:return (x-1)*(y-1)return 0if N==2:M=f(A[0],A[1])print(M)print(1,2)exit()if N==3:ans1=(f(A[2],f(A[0],A[1])),(1,2),(1,2))ans2=(f(A[0],f(A[1],A[2])),(2,3),(1,2))ans3=(f(A[1],f(A[0],A[2])),(1,3),(1,2))ls=[ans1,ans2,ans3]ls.sort()print(ls[0][0])print(*ls[0][1])print(*ls[0][2])exit()print(0)print(1,2)print(1,2)print(N-3,N-2)for i in range(N-3,1,-1):print(1,i)