結果
問題 | No.1730 GCD on Blackboard in yukicoder |
ユーザー |
|
提出日時 | 2021-11-05 22:08:36 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,154 ms / 2,000 ms |
コード長 | 651 bytes |
コンパイル時間 | 2,270 ms |
コンパイル使用メモリ | 168,200 KB |
実行使用メモリ | 8,856 KB |
最終ジャッジ日時 | 2024-11-08 04:40:52 |
合計ジャッジ時間 | 14,265 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 24 |
ソースコード
#include <bits/stdc++.h> #define rep(i, l, r) for (int i = (l); i < (r); i++) using namespace std; typedef long long ll; int main() { int N; cin >> N; vector<int> A(N), D(1000001, 0), ans(N, 1); rep(i, 0, N) cin >> A[i]; rep(i, 0, N) { for (int j = 1; j * j <= A[i]; j++) { if (A[i] % j == 0) { D[j]++; if (j * j != A[i]) D[A[i] / j]++; } } } rep(i, 1, 1000001) { if (D[i] == 0) continue; ans[N - D[i]] = i; } rep(i, 0, N) { if (i > 0) ans[i] = max(ans[i], ans[i - 1]); cout << ans[i] << endl; } }