結果
問題 |
No.1746 Sqrt Integer Segments
|
ユーザー |
|
提出日時 | 2021-11-28 02:49:55 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 589 ms / 2,000 ms |
コード長 | 1,018 bytes |
コンパイル時間 | 161 ms |
コンパイル使用メモリ | 82,192 KB |
実行使用メモリ | 131,312 KB |
最終ジャッジ日時 | 2024-09-13 09:29:14 |
合計ジャッジ時間 | 16,721 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 28 |
ソースコード
import sys,random,bisect from collections import deque,defaultdict from heapq import heapify,heappop,heappush from itertools import permutations from math import log,gcd input = lambda :sys.stdin.readline() mi = lambda :map(int,input().split()) li = lambda :list(mi()) 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(i,M+1,i): spf[j] = i def factorize(n): res = [] while n!=1: p = spf[n] cnt = 0 while n%p==0: cnt += 1 n //= p if cnt&1: res.append(p) return res rand_val = [random.randint(0,(1<<60)-1) for i in range(M+1)] N = int(input()) A = [1] + li() hash = [0 for i in range(N+1)] for i in range(N+1): tmp_p = factorize(A[i]) for p in tmp_p: hash[i] ^= rand_val[p] for i in range(1,N+1): hash[i] ^= hash[i-1] dic = {val:0 for val in hash} for val in hash: dic[val] += 1 res = sum(k*(k-1)//2 for val,k in dic.items()) print(res)