Submission #8012845
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 | Python (3.4.3) |
Score | 0 |
Code Size | 1020 Byte |
Status | RE |
Exec Time | 652 ms |
Memory | 719232 KB |
Judge Result
Set Name | Sample | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 400 | ||||||||
Status |
|
|
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 | 35 ms | 5048 KB |
00_example_02.txt | AC | 35 ms | 5048 KB |
00_example_03.txt | AC | 36 ms | 5048 KB |
10_random_01.txt | AC | 35 ms | 5092 KB |
10_random_02.txt | AC | 57 ms | 38244 KB |
10_random_03.txt | AC | 37 ms | 6372 KB |
10_random_04.txt | AC | 71 ms | 61028 KB |
10_random_05.txt | AC | 35 ms | 5092 KB |
20_max_01.txt | AC | 177 ms | 21968 KB |
20_max_02.txt | AC | 170 ms | 22960 KB |
20_max_03.txt | MLE | 652 ms | 719232 KB |
20_max_04.txt | AC | 164 ms | 22864 KB |
20_max_05.txt | AC | 256 ms | 24052 KB |
30_overflow_01.txt | AC | 172 ms | 20576 KB |
30_overflow_02.txt | AC | 172 ms | 20576 KB |
40_dmax_01.txt | RE | 87 ms | 23228 KB |
40_dmax_02.txt | RE | 87 ms | 23224 KB |
40_dmax_03.txt | RE | 86 ms | 23212 KB |
50_prime_01.txt | AC | 177 ms | 21736 KB |
50_prime_02.txt | AC | 203 ms | 23516 KB |
50_prime_03.txt | RE | 86 ms | 22988 KB |
60_prime_pow_01.txt | RE | 84 ms | 22968 KB |
60_prime_pow_02.txt | MLE | 553 ms | 554744 KB |
60_prime_pow_03.txt | RE | 86 ms | 22676 KB |
70_one_01.txt | AC | 137 ms | 20380 KB |