Submission #7709951


Source Code Expand

from fractions import gcd
from collections import Counter
n,k=map(int,input().split())
a=list(map(int,input().split()))
l=[]
for i in range(n):
  l.append(gcd(a[i],k))
l=Counter(l)
L=list(l.keys())
L2=list(l.values())
ct=0
for i in range(len(l)):
  for j in range(i,len(l)):
    if (L[i]*L[j])%k==0:
      if i!=j:
        ct+=L2[i]*L2[j]
      else:
        ct+=(L2[i]*(L2[i]-1)//2)
print(ct)

Submission Info

Submission Time
Task C - ロト2
User akariki
Language Python (3.4.3)
Score 400
Code Size 411 Byte
Status AC
Exec Time 513 ms
Memory 29116 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 25
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt, 00_example_03.txt
All 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 10_random_01.txt, 10_random_02.txt, 10_random_03.txt, 10_random_04.txt, 10_random_05.txt, 20_max_01.txt, 20_max_02.txt, 20_max_03.txt, 20_max_04.txt, 20_max_05.txt, 30_overflow_01.txt, 30_overflow_02.txt, 40_dmax_01.txt, 40_dmax_02.txt, 40_dmax_03.txt, 50_prime_01.txt, 50_prime_02.txt, 50_prime_03.txt, 60_prime_pow_01.txt, 60_prime_pow_02.txt, 60_prime_pow_03.txt, 70_one_01.txt
Case Name Status Exec Time Memory
00_example_01.txt AC 36 ms 5048 KB
00_example_02.txt AC 35 ms 5048 KB
00_example_03.txt AC 38 ms 5048 KB
10_random_01.txt AC 37 ms 5088 KB
10_random_02.txt AC 37 ms 5088 KB
10_random_03.txt AC 37 ms 5088 KB
10_random_04.txt AC 36 ms 5088 KB
10_random_05.txt AC 37 ms 5048 KB
20_max_01.txt AC 200 ms 26528 KB
20_max_02.txt AC 192 ms 26220 KB
20_max_03.txt AC 255 ms 29116 KB
20_max_04.txt AC 189 ms 26124 KB
20_max_05.txt AC 282 ms 27184 KB
30_overflow_01.txt AC 197 ms 24760 KB
30_overflow_02.txt AC 195 ms 24628 KB
40_dmax_01.txt AC 457 ms 27920 KB
40_dmax_02.txt AC 461 ms 27916 KB
40_dmax_03.txt AC 513 ms 28048 KB
50_prime_01.txt AC 200 ms 26256 KB
50_prime_02.txt AC 225 ms 26524 KB
50_prime_03.txt AC 256 ms 27672 KB
60_prime_pow_01.txt AC 262 ms 27716 KB
60_prime_pow_02.txt AC 255 ms 27408 KB
60_prime_pow_03.txt AC 248 ms 27392 KB
70_one_01.txt AC 156 ms 24372 KB