Submission #969811
Source Code Expand
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.*; public class Main { static BufferedReader in; static PrintWriter out; static StringTokenizer tok; void solve() throws IOException { int n = ni(); int k = ni(); int[] a = nia(n); HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 1; i * i <= k; i++) { if (k % i == 0) { map.put(i, 0); map.put(k / i, 0); } } for (int i = 0; i < n; i++) { int x = gcd(a[i], k); map.put(x, map.get(x) + 1); } Set<Integer> set = map.keySet(); long ans = 0; for (int x : set) { for (int y : set) { if ((long) x * y % k == 0) { if (x != y) { ans += (long) map.get(x) * map.get(y); } else { ans += (long) (map.get(x) - 1) * map.get(x); } } } } out.println(ans / 2); } int gcd(int a, int b) { return a == 0 ? b : gcd(b % a, a); } String ns() throws IOException { while (!tok.hasMoreTokens()) { tok = new StringTokenizer(in.readLine(), " "); } return tok.nextToken(); } int ni() throws IOException { return Integer.parseInt(ns()); } long nl() throws IOException { return Long.parseLong(ns()); } double nd() throws IOException { return Double.parseDouble(ns()); } String[] nsa(int n) throws IOException { String[] res = new String[n]; for (int i = 0; i < n; i++) { res[i] = ns(); } return res; } int[] nia(int n) throws IOException { int[] res = new int[n]; for (int i = 0; i < n; i++) { res[i] = ni(); } return res; } long[] nla(int n) throws IOException { long[] res = new long[n]; for (int i = 0; i < n; i++) { res[i] = nl(); } return res; } public static void main(String[] args) throws IOException { in = new BufferedReader(new InputStreamReader(System.in)); out = new PrintWriter(System.out); tok = new StringTokenizer(""); Main main = new Main(); main.solve(); out.close(); } }
Submission Info
Submission Time | |
---|---|
Task | C - ロト2 |
User | CrazyBBB |
Language | Java8 (OpenJDK 1.8.0) |
Score | 400 |
Code Size | 2615 Byte |
Status | AC |
Exec Time | 429 ms |
Memory | 36684 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 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 | 95 ms | 8272 KB |
00_example_02.txt | AC | 96 ms | 8144 KB |
00_example_03.txt | AC | 97 ms | 8140 KB |
10_random_01.txt | AC | 100 ms | 8528 KB |
10_random_02.txt | AC | 109 ms | 8780 KB |
10_random_03.txt | AC | 108 ms | 8272 KB |
10_random_04.txt | AC | 112 ms | 8524 KB |
10_random_05.txt | AC | 100 ms | 8528 KB |
20_max_01.txt | AC | 294 ms | 32504 KB |
20_max_02.txt | AC | 308 ms | 33700 KB |
20_max_03.txt | AC | 301 ms | 35596 KB |
20_max_04.txt | AC | 290 ms | 29848 KB |
20_max_05.txt | AC | 295 ms | 30888 KB |
30_overflow_01.txt | AC | 293 ms | 32336 KB |
30_overflow_02.txt | AC | 281 ms | 32960 KB |
40_dmax_01.txt | AC | 421 ms | 36684 KB |
40_dmax_02.txt | AC | 418 ms | 36420 KB |
40_dmax_03.txt | AC | 429 ms | 36204 KB |
50_prime_01.txt | AC | 310 ms | 32768 KB |
50_prime_02.txt | AC | 293 ms | 30248 KB |
50_prime_03.txt | AC | 304 ms | 35088 KB |
60_prime_pow_01.txt | AC | 320 ms | 35424 KB |
60_prime_pow_02.txt | AC | 303 ms | 34944 KB |
60_prime_pow_03.txt | AC | 304 ms | 35472 KB |
70_one_01.txt | AC | 283 ms | 31932 KB |