Submission #7420182
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); } } divisors.Sort(); var dict = new Dictionary<long, long>(); for(int i = 0; i < divisors.Count; i++) dict[divisors[i]] = i; long ans = 0; long[] cnt = new long[divisors.Count]; for(int i = N - 1; i>= 0; i--) { long g = gcd(A[i], K); ans += cnt[dict[K / g]]; for(int j = 0; j < divisors.Count; j++) if(A[i] % divisors[j] == 0) cnt[dict[divisors[j]]]++; } Console.WriteLine(ans); } 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 | 0 |
Code Size | 2039 Byte |
Status | TLE |
Exec Time | 2109 ms |
Memory | 34780 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 | 29 ms | 11360 KB |
00_example_02.txt | AC | 27 ms | 9312 KB |
00_example_03.txt | AC | 29 ms | 11476 KB |
10_random_01.txt | AC | 29 ms | 11488 KB |
10_random_02.txt | AC | 30 ms | 13536 KB |
10_random_03.txt | AC | 28 ms | 11360 KB |
10_random_04.txt | AC | 29 ms | 11488 KB |
10_random_05.txt | AC | 29 ms | 11360 KB |
20_max_01.txt | AC | 191 ms | 27996 KB |
20_max_02.txt | AC | 152 ms | 29788 KB |
20_max_03.txt | AC | 208 ms | 32860 KB |
20_max_04.txt | AC | 170 ms | 31868 KB |
20_max_05.txt | AC | 213 ms | 33312 KB |
30_overflow_01.txt | AC | 202 ms | 29020 KB |
30_overflow_02.txt | AC | 202 ms | 31068 KB |
40_dmax_01.txt | TLE | 2109 ms | 31324 KB |
40_dmax_02.txt | TLE | 2109 ms | 29788 KB |
40_dmax_03.txt | TLE | 2109 ms | 31836 KB |
50_prime_01.txt | AC | 158 ms | 31964 KB |
50_prime_02.txt | AC | 173 ms | 34780 KB |
50_prime_03.txt | AC | 215 ms | 33244 KB |
60_prime_pow_01.txt | AC | 323 ms | 30400 KB |
60_prime_pow_02.txt | AC | 196 ms | 33372 KB |
60_prime_pow_03.txt | AC | 181 ms | 31452 KB |
70_one_01.txt | AC | 138 ms | 28124 KB |