結果
問題 | No.1730 GCD on Blackboard in yukicoder |
ユーザー |
![]() |
提出日時 | 2021-11-05 22:03:20 |
言語 | Java (openjdk 23) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,335 bytes |
コンパイル時間 | 2,968 ms |
コンパイル使用メモリ | 78,292 KB |
実行使用メモリ | 79,856 KB |
最終ジャッジ日時 | 2024-11-06 12:53:56 |
合計ジャッジ時間 | 26,080 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 TLE * 2 |
ソースコード
import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.PrintWriter;import java.util.ArrayList;import java.util.List;public class Main {public static void main(String[] args) throws Exception {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(br.readLine());String[] sa = br.readLine().split(" ");int[] a = new int[n];for (int i = 0; i < n; i++) {a[i] = Integer.parseInt(sa[i]);}br.close();int[] cnt = new int[1000001];for (int i = 0; i < n; i++) {List<Integer> list = divList(a[i]);for (int e : list) {cnt[e]++;}}int[] ans = new int[n];for (int i = 1000000; i > 0; i--) {if (cnt[i] > 0) {int x = n - cnt[i];if (ans[x] == 0) {ans[x] = i;}}}for (int i = 1; i < n; i++) {ans[i] = Math.max(ans[i], ans[i - 1]);}PrintWriter pw = new PrintWriter(System.out);for (int i : ans) {pw.println(i);}pw.flush();}static List<Integer> divList(int n) {List<Integer> list = new ArrayList<>();int end = (int) Math.sqrt(n);for (int i = 1; i <= end; i++) {if (n % i == 0) {list.add(i);}}int i = end * end == n ? list.size() - 2 : list.size() - 1;for ( ; i >= 0; i--) {list.add(n / list.get(i));}return list;}}