Submission #50604911

Source Code Expand

#ABC342_20240224_D
import collections
N=int(input())
A=list(map(int,input().split()))
L=[4, 9, 25, 49, 121, 169, 289, 361, 529, 841, 961, 1369, 1681, 1849, 2209, 2809, 3481, 3721, 4489, 5041, 5329, 6241, 6889, 7921, 9409, 10201, 10609, 11449, 11881, 12769, 16129, 17161, 18769, 19321, 22201, 22801, 24649, 26569, 27889, 29929, 32041, 32761, 36481, 37249, 38809, 39601, 44521, 49729, 51529, 52441, 54289, 57121, 58081, 63001, 66049, 69169, 72361, 73441, 76729, 78961, 80089, 85849, 94249, 96721, 97969, 100489, 109561, 113569, 120409, 121801, 124609, 128881, 134689, 139129, 143641, 146689, 151321, 157609, 160801, 167281, 175561, 177241, 185761, 187489, 192721, 196249, 201601]
ans=0
P=[]
N2=N
for i in range(N):
    if(A[i]==0):
        N2-=1
        ans+=N2
    else:
        j=0
        p=A[i]
        while(L[j]<=p and p!=1):
            if(p%L[j]==0):
                p//=L[j]
                j=0
            else:
                j+=1
        P.append(p)
#print(P)
PN=collections.Counter(P)
for x in PN.values():
    if(x>1):
        ans+=(x*(x-1))//2
print(ans)

Submission Info

Submission Time
Task D - Square Pair
User Konini
Language Python (PyPy 3.10-v7.3.12)
Score 400
Code Size 1097 Byte
Status AC
Exec Time 167 ms
Memory 139324 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 2
AC × 17
Set Name Test Cases
Sample 00_sample_01.txt, 00_sample_02.txt
All 00_sample_01.txt, 00_sample_02.txt, 01_test_01.txt, 01_test_02.txt, 01_test_03.txt, 01_test_04.txt, 01_test_05.txt, 01_test_06.txt, 01_test_07.txt, 01_test_08.txt, 01_test_09.txt, 01_test_10.txt, 01_test_11.txt, 01_test_12.txt, 01_test_13.txt, 01_test_14.txt, 01_test_15.txt
Case Name Status Exec Time Memory
00_sample_01.txt AC 68 ms 76812 KiB
00_sample_02.txt AC 70 ms 76820 KiB
01_test_01.txt AC 166 ms 139324 KiB
01_test_02.txt AC 133 ms 121976 KiB
01_test_03.txt AC 93 ms 104044 KiB
01_test_04.txt AC 140 ms 121176 KiB
01_test_05.txt AC 148 ms 124508 KiB
01_test_06.txt AC 157 ms 128788 KiB
01_test_07.txt AC 129 ms 120064 KiB
01_test_08.txt AC 130 ms 119764 KiB
01_test_09.txt AC 69 ms 76992 KiB
01_test_10.txt AC 70 ms 76644 KiB
01_test_11.txt AC 85 ms 83896 KiB
01_test_12.txt AC 167 ms 134564 KiB
01_test_13.txt AC 143 ms 116840 KiB
01_test_14.txt AC 87 ms 84768 KiB
01_test_15.txt AC 149 ms 121808 KiB