結果
問題 | No.990 N×Mマス計算(Kの倍数) |
ユーザー |
![]() |
提出日時 | 2022-08-30 12:41:09 |
言語 | Java (openjdk 23) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,484 bytes |
コンパイル時間 | 3,600 ms |
コンパイル使用メモリ | 80,012 KB |
実行使用メモリ | 58,204 KB |
最終ジャッジ日時 | 2024-11-07 07:52:34 |
合計ジャッジ時間 | 8,566 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 10 TLE * 1 -- * 8 |
ソースコード
import java.io.*;import java.util.*;public class Main {public static void main(String[] args) throws Exception {Scanner sc = new Scanner();int n = sc.nextInt();int m = sc.nextInt();int k = sc.nextInt();if (sc.next().charAt(0) == '+') {HashMap<Integer, Long> bCounts = new HashMap<>();for (int i = 0; i < m; i++) {int x = sc.nextInt() % k;bCounts.put(x, bCounts.getOrDefault(x, 0L) + 1);}HashMap<Integer, Long> aCounts = new HashMap<>();for (int i = 0; i < n; i++) {int x = sc.nextInt() % k;aCounts.put(x, aCounts.getOrDefault(x, 0L) + 1);}long ans = 0;for (int x : bCounts.keySet()) {if (x == 0) {ans += aCounts.getOrDefault(x, 0L) * bCounts.get(x);} else {ans += aCounts.getOrDefault(k - x, 0L) * bCounts.get(x);}}System.out.println(ans);} else {HashMap<Integer, Integer> base = new HashMap<>();int kk = k;for (int i = 2; i <= Math.sqrt(kk); i++) {while (kk % i == 0) {base.put(i, base.getOrDefault(i, 0) + 1);kk /= i;}}if (kk > 1) {base.put(kk, base.getOrDefault(kk, 0) + 1);}int idx = 0;Count.baseValue = new int[base.size()];Count.baseCount = new int[base.size()];for (int x : base.keySet()) {Count.baseValue[idx] = x;Count.baseCount[idx] = base.get(x);idx++;}Count.length = idx;HashMap<Count, Long> bCounts = new HashMap<>();for (int i = 0; i < m; i++) {Count x = new Count(sc.nextInt());bCounts.put(x, bCounts.getOrDefault(x, 0L) + 1);}HashMap<Count, Long> aCounts = new HashMap<>();for (int i = 0; i < n; i++) {Count x = new Count(sc.nextInt());aCounts.put(x, aCounts.getOrDefault(x, 0L) + 1);}long ans = 0;for (Count x : bCounts.keySet()) {for (Count y : aCounts.keySet()) {if (x.hasK(y)) {ans += bCounts.get(x) * aCounts.get(y);}}}System.out.println(ans);}}static class Count {static int[] baseValue;static int[] baseCount;static int length;int[] counts;public Count(int x) {counts = new int[length];for (int i = 0; i < length; i++) {while (x % baseValue[i] == 0) {counts[i]++;x /= baseValue[i];}counts[i] = Math.min(counts[i], baseCount[i]);}}public boolean hasK(Count another) {for (int i = 0; i < length; i++) {if (counts[i] + another.counts[i] < baseCount[i]) {return false;}}return true;}public int hashCode() {return 0;}public boolean equals(Object o) {Count c = (Count)o;for (int i = 0; i < length; i++) {if (counts[i] != c.counts[i]) {return false;}}return true;}}}class Scanner {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StringTokenizer st = new StringTokenizer("");StringBuilder sb = new StringBuilder();public Scanner() throws Exception {}public int nextInt() throws Exception {return Integer.parseInt(next());}public long nextLong() throws Exception {return Long.parseLong(next());}public double nextDouble() throws Exception {return Double.parseDouble(next());}public String next() throws Exception {while (!st.hasMoreTokens()) {st = new StringTokenizer(br.readLine());}return st.nextToken();}}