Submission #5412996


Source Code Expand

Copy
N,K=map(int,input().split())
A=list(map(int,input().split()))
def gcd(a,b):
    while a%b!=0:
        a,b=b,a%b
    return b
for i,a in enumerate(A):
    A[i]=gcd(a,K)
from collections import defaultdict
cnt=defaultdict(int)
for a in A:
    cnt[a]+=1
yakusu=set()
for i in range(1,int(K**0.5)+1):
    if K%i==0:
        yakusu|={i,K//i}
if K==1:
    yakusu|={1}

ans=0
for x in yakusu:
    for y in yakusu:
        if x>y or x*y%K!=0:
            continue
        elif x==y:
            ans+=cnt[x]*(cnt[x]-1)//2
        else:
            ans+=cnt[x]*cnt[y]
print(ans)

Submission Info

Submission Time
Task C - ロト2
User gratan
Language Python3 (3.4.3)
Score 400
Code Size 596 Byte
Status
Exec Time 623 ms
Memory 27308 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 20 ms 3316 KB
00_example_02.txt 20 ms 3316 KB
00_example_03.txt 20 ms 3316 KB
10_random_01.txt 21 ms 3316 KB
10_random_02.txt 22 ms 3316 KB
10_random_03.txt 21 ms 3316 KB
10_random_04.txt 21 ms 3316 KB
10_random_05.txt 20 ms 3316 KB
20_max_01.txt 232 ms 23908 KB
20_max_02.txt 220 ms 22588 KB
20_max_03.txt 342 ms 24812 KB
20_max_04.txt 213 ms 23788 KB
20_max_05.txt 418 ms 25708 KB
30_overflow_01.txt 231 ms 22824 KB
30_overflow_02.txt 227 ms 22784 KB
40_dmax_01.txt 606 ms 24316 KB
40_dmax_02.txt 623 ms 24316 KB
40_dmax_03.txt 586 ms 25184 KB
50_prime_01.txt 240 ms 23904 KB
50_prime_02.txt 289 ms 24416 KB
50_prime_03.txt 342 ms 27308 KB
60_prime_pow_01.txt 329 ms 25100 KB
60_prime_pow_02.txt 329 ms 26056 KB
60_prime_pow_03.txt 332 ms 23744 KB
70_one_01.txt 154 ms 22292 KB