結果
問題 | No.990 N×Mマス計算(Kの倍数) |
ユーザー | mban |
提出日時 | 2020-03-12 13:54:56 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 1,750 ms / 2,000 ms |
コード長 | 6,909 bytes |
コンパイル時間 | 2,478 ms |
コンパイル使用メモリ | 116,348 KB |
実行使用メモリ | 37,632 KB |
最終ジャッジ日時 | 2024-11-17 20:47:41 |
合計ジャッジ時間 | 7,102 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 24 ms
18,048 KB |
testcase_01 | AC | 24 ms
18,176 KB |
testcase_02 | AC | 27 ms
17,920 KB |
testcase_03 | AC | 24 ms
18,048 KB |
testcase_04 | AC | 24 ms
18,048 KB |
testcase_05 | AC | 25 ms
17,920 KB |
testcase_06 | AC | 25 ms
17,920 KB |
testcase_07 | AC | 25 ms
18,048 KB |
testcase_08 | AC | 24 ms
17,920 KB |
testcase_09 | AC | 24 ms
18,048 KB |
testcase_10 | AC | 79 ms
30,848 KB |
testcase_11 | AC | 91 ms
29,696 KB |
testcase_12 | AC | 1,739 ms
32,768 KB |
testcase_13 | AC | 68 ms
24,812 KB |
testcase_14 | AC | 103 ms
28,416 KB |
testcase_15 | AC | 77 ms
24,448 KB |
testcase_16 | AC | 98 ms
30,720 KB |
testcase_17 | AC | 63 ms
24,704 KB |
testcase_18 | AC | 1,750 ms
32,640 KB |
testcase_19 | AC | 510 ms
27,136 KB |
testcase_20 | AC | 141 ms
37,632 KB |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.Collections.Generic; using CompLib.Collections; using CompLib.Mathematics; using CompLib.Util; class Program { private int N, M, K; private char op; private int[] B; private int[] A; public void Solve() { var sc = new Scanner(); N = sc.NextInt(); M = sc.NextInt(); K = sc.NextInt(); op = sc.NextChar(); B = new int[M]; for (int i = 0; i < M; i++) { B[i] = sc.NextInt(); } A = new int[N]; for (int i = 0; i < N; i++) { A[i] = sc.NextInt(); } if (op == '+') { Plus(); } else if (op == '*') { Mul(); } } void Plus() { var map = new HashMap<int, int>(); for (int i = 0; i < N; i++) { map[A[i] % K]++; } var map2 = new HashMap<int, int>(); for (int i = 0; i < M; i++) { map2[B[i] % K]++; } long ans = 0; foreach (KeyValuePair<int, int> pair in map2) { if (pair.Key == 0) ans += (long) pair.Value * map[0]; else ans += (long) pair.Value * map[K - pair.Key]; } Console.WriteLine(ans); } void Mul() { // kの約数列挙 var l = new List<int>(); for (int t = 1; t * t <= K; t++) { if (K % t == 0) { l.Add(t); if (t * t != K) l.Add(K / t); } } var map = new HashMap<int, int>(); foreach (int i in A) { foreach (int j in l) { if (i % j == 0) map[j]++; } } long ans = 0; foreach (int i in B) { var gcd = MathEx.GCD(i, K); ans += map[K / gcd]; } Console.WriteLine(ans); } public static void Main(string[] args) => new Program().Solve(); } // https://bitbucket.org/camypaper/complib namespace CompLib.Mathematics { using System; using System.Collections.Generic; #region GCD LCM /// <summary> /// 様々な数学的関数の静的メソッドを提供します. /// </summary> public static partial class MathEx { /// <summary> /// 2 つの整数の最大公約数を求めます. /// </summary> /// <param name="n">最初の値</param> /// <param name="m">2 番目の値</param> /// <returns>2 つの整数の最大公約数</returns> /// <remarks>ユークリッドの互除法に基づき最悪計算量 O(log N) で実行されます.</remarks> public static int GCD(int n, int m) { return (int) GCD((long) n, m); } /// <summary> /// 2 つの整数の最大公約数を求めます. /// </summary> /// <param name="n">最初の値</param> /// <param name="m">2 番目の値</param> /// <returns>2 つの整数の最大公約数</returns> /// <remarks>ユークリッドの互除法に基づき最悪計算量 O(log N) で実行されます.</remarks> public static long GCD(long n, long m) { n = Math.Abs(n); m = Math.Abs(m); while (n != 0) { m %= n; if (m == 0) return n; n %= m; } return m; } /// <summary> /// 2 つの整数の最小公倍数を求めます. /// </summary> /// <param name="n">最初の値</param> /// <param name="m">2 番目の値</param> /// <returns>2 つの整数の最小公倍数</returns> /// <remarks>最悪計算量 O(log N) で実行されます.</remarks> public static long LCM(long n, long m) { return (n / GCD(n, m)) * m; } } #endregion #region PrimeSieve public static partial class MathEx { /// <summary> /// ある値までに素数表を構築します. /// </summary> /// <param name="max">最大の値</param> /// <param name="primes">素数のみを入れた数列が返される</param> /// <returns>0 から max までの素数表</returns> /// <remarks>エラトステネスの篩に基づき,最悪計算量 O(N loglog N) で実行されます.</remarks> public static bool[] Sieve(int max, List<int> primes = null) { var isPrime = new bool[max + 1]; for (int i = 2; i < isPrime.Length; i++) isPrime[i] = true; for (int i = 2; i * i <= max; i++) if (!isPrime[i]) continue; else for (int j = i * i; j <= max; j += i) isPrime[j] = false; if (primes != null) for (int i = 0; i <= max; i++) if (isPrime[i]) primes.Add(i); return isPrime; } } #endregion } namespace CompLib.Collections { using System.Collections.Generic; public class HashMap<TKey, TValue> : Dictionary<TKey, TValue> { public new TValue this[TKey key] { get { TValue o; return TryGetValue(key, out o) ? o : default(TValue); } set { base[key] = value; } } } } namespace CompLib.Util { using System; using System.Linq; class Scanner { private string[] _line; private int _index; private const char Separator = ' '; public Scanner() { _line = new string[0]; _index = 0; } public string Next() { while (_index >= _line.Length) { _line = Console.ReadLine().Split(Separator); _index = 0; } return _line[_index++]; } public int NextInt() => int.Parse(Next()); public long NextLong() => long.Parse(Next()); public double NextDouble() => double.Parse(Next()); public decimal NextDecimal() => decimal.Parse(Next()); public char NextChar() => Next()[0]; public char[] NextCharArray() => Next().ToCharArray(); public string[] Array() { _line = Console.ReadLine().Split(' '); _index = _line.Length; return _line; } public int[] IntArray() => Array().Select(int.Parse).ToArray(); public long[] LongArray() => Array().Select(long.Parse).ToArray(); public double[] DoubleArray() => Array().Select(double.Parse).ToArray(); public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray(); } }