Contest Duration: ~ (local time)

Submission #5412988

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)+2):
if K%i==0 and K//i!=i:
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 and cnt[x]>1:
ans+=cnt[x]*(cnt[x]-1)//2
else:
ans+=cnt[x]*cnt[y]
print(ans)```

Submission Info

Submission Time 2019-05-16 11:23:40+0900 C - ロト2 gratan Python3 (3.4.3) 0 621 Byte WA 597 ms 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 0 / 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 21 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 230 ms 23312 KB
20_max_02.txt 221 ms 23904 KB
20_max_03.txt 340 ms 25556 KB
20_max_04.txt 213 ms 23788 KB
20_max_05.txt 418 ms 25200 KB
30_overflow_01.txt 231 ms 23424 KB
30_overflow_02.txt 232 ms 23668 KB
40_dmax_01.txt 587 ms 24316 KB
40_dmax_02.txt 575 ms 25340 KB
40_dmax_03.txt 597 ms 26020 KB
50_prime_01.txt 242 ms 23900 KB
50_prime_02.txt 290 ms 26016 KB
50_prime_03.txt 342 ms 27308 KB
60_prime_pow_01.txt 327 ms 25100 KB
60_prime_pow_02.txt 330 ms 23932 KB
60_prime_pow_03.txt 330 ms 23748 KB
70_one_01.txt 154 ms 22804 KB