結果
問題 | 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; } }