結果
問題 |
No.368 LCM of K-products
|
ユーザー |
![]() |
提出日時 | 2019-11-21 12:56:20 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 418 ms / 2,000 ms |
コード長 | 1,734 bytes |
コンパイル時間 | 2,540 ms |
コンパイル使用メモリ | 80,092 KB |
実行使用メモリ | 61,400 KB |
最終ジャッジ日時 | 2024-10-09 16:50:23 |
合計ジャッジ時間 | 10,845 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 35 |
ソースコード
import java.util.*; public class Main { static final int MOD = 1000000007; public static void main (String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); HashMap<Integer, ArrayList<Integer>> allMap = new HashMap<>(); for (int i = 0; i < n; i++) { HashMap<Integer, Integer> map = new HashMap<>(); int x = sc.nextInt(); for (int j = 2; j <= Math.sqrt(x); j++) { while (x % j == 0) { if (map.containsKey(j)) { map.put(j, map.get(j) + 1); } else { map.put(j, 1); } x /= j; } } if (x != 1) { if (map.containsKey(x)) { map.put(x, map.get(x) + 1); } else { map.put(x, 1); } } for (Map.Entry<Integer, Integer> entry : map.entrySet()) { if (!allMap.containsKey(entry.getKey())) { allMap.put(entry.getKey(), new ArrayList<Integer>()); } allMap.get(entry.getKey()).add(entry.getValue()); } } long total = 1; for (Map.Entry<Integer, ArrayList<Integer>> entry : allMap.entrySet()) { ArrayList<Integer> list = entry.getValue(); Collections.sort(list); int sum = 0; for (int i = 0; i < list.size() && i < k; i++) { sum += list.get(list.size() - i - 1); } total *= pow(entry.getKey(), sum); total %= MOD; } System.out.println(total); } static long pow(int base, int power) { long ans = 1; for (int i = 0; i < power; i++) { ans *= base; ans %= MOD; } return ans; } }