Submission #8012836


Source Code Expand

#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict
from fractions import gcd

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, K = getlist()
	A = getlist()
	G = []
	if ((K ** 0.5) // 1) ** 2 == K:
		x = int((K ** 0.5) // 1)
		for i in range(1, x):
			if K % i == 0:
				G.append(i)
		n = len(G)
		for i in range(n):
			G.append(K // G[i])
		G.append(int((K ** 0.5) // 1))

	else:
		x = int((K ** 0.5) // 1)
		for i in range(1, x + 1):
			if K % i == 0:
				G.append(i)
		n = len(G)
		for i in range(n):
			G.append(K // G[i])

	D = [0] * (K + 1)
	for i in range(N):
		D[gcd(A[i], K)] += 1
	
	ans = 0
	n = len(G)
	for i in range(n):
		for j in range(i, n):
			if (G[i] * G[j]) % K == 0:
				if i != j:
					ans += (D[G[i]] * D[G[j]])
				else:
					ans += ((D[G[i]] - 1) * D[G[j]]) // 2
	print(ans)

	


if __name__ == '__main__':
	main()

Submission Info

Submission Time
Task C - ロト2
User su_565fx
Language PyPy3 (2.4.0)
Score 0
Code Size 1020 Byte
Status RE
Exec Time 638 ms
Memory 755520 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 3
AC × 17
MLE × 2
RE × 6
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 306 ms 66476 KB
00_example_02.txt AC 272 ms 63852 KB
00_example_03.txt AC 271 ms 63852 KB
10_random_01.txt AC 270 ms 63852 KB
10_random_02.txt AC 288 ms 97516 KB
10_random_03.txt AC 269 ms 65132 KB
10_random_04.txt AC 301 ms 102012 KB
10_random_05.txt AC 279 ms 63852 KB
20_max_01.txt AC 377 ms 97004 KB
20_max_02.txt AC 361 ms 96748 KB
20_max_03.txt MLE 638 ms 755520 KB
20_max_04.txt AC 363 ms 96748 KB
20_max_05.txt AC 409 ms 99180 KB
30_overflow_01.txt AC 358 ms 94956 KB
30_overflow_02.txt AC 357 ms 94956 KB
40_dmax_01.txt RE 351 ms 100588 KB
40_dmax_02.txt RE 352 ms 100588 KB
40_dmax_03.txt RE 343 ms 100588 KB
50_prime_01.txt AC 360 ms 96748 KB
50_prime_02.txt AC 380 ms 98540 KB
50_prime_03.txt RE 346 ms 100588 KB
60_prime_pow_01.txt RE 343 ms 98796 KB
60_prime_pow_02.txt MLE 592 ms 591232 KB
60_prime_pow_03.txt RE 342 ms 98796 KB
70_one_01.txt AC 344 ms 95212 KB