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
Task C - ロト2
User gratan
Language Python3 (3.4.3)
Score 0
Code Size 621 Byte
Status
Exec Time 597 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 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