Submission #5391050


Source Code Expand

Copy
from math import floor
from fractions import gcd
from collections import Counter

N,K = map(int,input().split())
A = list(map(int,input().split()))

A = [gcd(K,a) for a in A]
C = Counter(A).items()
ans = 0

for a,cnt1 in C:
    for b,cnt2 in C:
        if a * b % K == 0:
            if a == b:
                ans += cnt1*(cnt2-1)
            else:
                ans += cnt1*cnt2

ans //= 2
print(ans)

Submission Info

Submission Time
Task C - ロト2
User pynomi
Language Python3 (3.4.3)
Score 400
Code Size 424 Byte
Status
Exec Time 568 ms
Memory 29324 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 00_example_01.txt, 00_example_02.txt, 00_example_03.txt
All 400 / 400 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 49 ms 5468 KB
00_example_02.txt 35 ms 5052 KB
00_example_03.txt 35 ms 5052 KB
10_random_01.txt 35 ms 5084 KB
10_random_02.txt 36 ms 5084 KB
10_random_03.txt 35 ms 5052 KB
10_random_04.txt 35 ms 5084 KB
10_random_05.txt 35 ms 5052 KB
20_max_01.txt 172 ms 25020 KB
20_max_02.txt 168 ms 25912 KB
20_max_03.txt 221 ms 27576 KB
20_max_04.txt 169 ms 25784 KB
20_max_05.txt 258 ms 27228 KB
30_overflow_01.txt 170 ms 23648 KB
30_overflow_02.txt 171 ms 23620 KB
40_dmax_01.txt 568 ms 26308 KB
40_dmax_02.txt 543 ms 27916 KB
40_dmax_03.txt 568 ms 27916 KB
50_prime_01.txt 175 ms 24744 KB
50_prime_02.txt 198 ms 28048 KB
50_prime_03.txt 220 ms 29324 KB
60_prime_pow_01.txt 214 ms 26208 KB
60_prime_pow_02.txt 218 ms 27400 KB
60_prime_pow_03.txt 215 ms 27336 KB
70_one_01.txt 141 ms 24540 KB