Submission #7420761
Source Code Expand
using System; using System.Collections; using System.Collections.Generic; using System.Text; using System.Linq; using static MyIO; public class C { public static void Main() => (new Solver()).Solve(); } public class Solver { public void Solve() { int N = GetInt(); long K = GetLong(); long[] A = GetLongs(N); var divisors = new List<long>((int)Math.Sqrt(K)); for(long i = 1; i * i <= K; i++) { if(K % i == 0) { divisors.Add(i); if(i * i < K) divisors.Add(K / i); } } var cnt = new Dictionary<long, long>(); for(int i = 0; i < N; i++) { long g = gcd(A[i], K); long current = 0; cnt.TryGetValue(g, out current); cnt[g] = current + 1; } long ans = 0; foreach(long x in cnt.Keys) { foreach(long y in cnt.Keys) { if((x * y) % K != 0) continue; ans += (x == y) ? cnt[x] * (cnt[x] - 1) : cnt[x] * cnt[y]; } } Console.WriteLine(ans / 2); } private long gcd(long x, long y) => (y == 0) ? x : gcd(y, x % y); } public static class MyIO { private static string[] args = null; private static int num = -1; private static int used = -1; private static string getArg() { if(used == num) { args = Console.ReadLine().Split(' '); num = args.Length; used = 0; } return args[used++]; } public static int GetInt() => int.Parse(getArg()); public static long GetLong() => long.Parse(getArg()); public static double GetDouble() => double.Parse(getArg()); public static string GetString() => getArg(); public static char GetChar() => getArg()[0]; public static int[] GetInts(int N) => Enumerable.Range(0, N).Select(_ => GetInt()).ToArray(); public static long[] GetLongs(int N) => Enumerable.Range(0, N).Select(_ => GetLong()).ToArray(); public static double[] GetDoubles(int N) => Enumerable.Range(0, N).Select(_ => GetDouble()).ToArray(); public static string[] GetStrings(int N) => Enumerable.Range(0, N).Select(_ => GetString()).ToArray(); }
Submission Info
Submission Time | |
---|---|
Task | C - ロト2 |
User | DM7PvTyc |
Language | C# (Mono 4.6.2.0) |
Score | 400 |
Code Size | 2048 Byte |
Status | AC |
Exec Time | 201 ms |
Memory | 37468 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 | 28 ms | 13408 KB |
00_example_02.txt | AC | 26 ms | 11360 KB |
00_example_03.txt | AC | 27 ms | 11360 KB |
10_random_01.txt | AC | 27 ms | 11360 KB |
10_random_02.txt | AC | 27 ms | 11360 KB |
10_random_03.txt | AC | 27 ms | 11360 KB |
10_random_04.txt | AC | 27 ms | 9312 KB |
10_random_05.txt | AC | 27 ms | 11476 KB |
20_max_01.txt | AC | 146 ms | 30044 KB |
20_max_02.txt | AC | 143 ms | 31708 KB |
20_max_03.txt | AC | 160 ms | 30812 KB |
20_max_04.txt | AC | 140 ms | 27740 KB |
20_max_05.txt | AC | 161 ms | 31128 KB |
30_overflow_01.txt | AC | 139 ms | 33116 KB |
30_overflow_02.txt | AC | 142 ms | 32988 KB |
40_dmax_01.txt | AC | 201 ms | 37468 KB |
40_dmax_02.txt | AC | 200 ms | 33372 KB |
40_dmax_03.txt | AC | 200 ms | 33628 KB |
50_prime_01.txt | AC | 149 ms | 29916 KB |
50_prime_02.txt | AC | 155 ms | 31588 KB |
50_prime_03.txt | AC | 161 ms | 29532 KB |
60_prime_pow_01.txt | AC | 159 ms | 33116 KB |
60_prime_pow_02.txt | AC | 159 ms | 30812 KB |
60_prime_pow_03.txt | AC | 160 ms | 32860 KB |
70_one_01.txt | AC | 131 ms | 28124 KB |