結果

問題 No.854 公平なりんご分配
コンテスト
ユーザー tenten
提出日時 2020-12-16 09:34:48
言語 Java
(openjdk 23)
結果
MLE  
実行時間 -
コード長 1,532 bytes
コンパイル時間 2,147 ms
コンパイル使用メモリ 79,620 KB
実行使用メモリ 565,172 KB
最終ジャッジ日時 2024-09-20 04:32:06
合計ジャッジ時間 102,157 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 39 WA * 24 TLE * 1 MLE * 17 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		ArrayList<HashMap<Integer, Integer>> apples = new ArrayList<>();
		apples.add(new HashMap<>());
		for (int i = 0; i < n; i++) {
		    HashMap<Integer, Integer> tmp = new HashMap<Integer, Integer>(apples.get(i));
		    int x = sc.nextInt();
		    for (int j = 2; j <= Math.sqrt(x); j++) {
		        while (x % j == 0) {
		            tmp.put(j, tmp.getOrDefault(j, 0) + 1);
		            x /= j;
		        }
		    }
		    if (x > 1) {
		        tmp.put(x, tmp.getOrDefault(x, 0) + 1);
		    }
		    apples.add(tmp);
		}
		int q = sc.nextInt();
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < q; i++) {
		    int p = sc.nextInt();
		    HashMap<Integer, Integer> left = apples.get(sc.nextInt() - 1);
		    HashMap<Integer, Integer> right = apples.get(sc.nextInt());
		    boolean can = true;
		    for (int j = 2; j <= Math.sqrt(p) && can; j++) {
		        if (p % j > 0) {
		            continue;
		        }
		        int count = right.getOrDefault(j, 0) - left.getOrDefault(j, 0);
		        while (p % j == 0) {
		            count--;
		            p /= j;
		        }
		        can = (count >= 0);
		    }
		    if (can && p > 1) {
		        can = (right.getOrDefault(p, 0) - left.getOrDefault(p, 0) >= 1);
		    }
		    if (can) {
		        sb.append("Yes");
		    } else {
		        sb.append("NO");
		    }
		    sb.append("\n");
		}
		System.out.print(sb);
	}
}
0