結果
| 問題 |
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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 19 |
コンパイルメッセージ
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();
}
}