結果
問題 |
No.1730 GCD on Blackboard in yukicoder
|
ユーザー |
![]() |
提出日時 | 2021-12-07 06:57:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 876 ms / 2,000 ms |
コード長 | 657 bytes |
コンパイル時間 | 1,946 ms |
コンパイル使用メモリ | 193,784 KB |
最終ジャッジ日時 | 2025-01-26 06:27:02 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 24 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector<int> A(N); vector<int> B(1000000 + 10, 0); for (auto&& e : A) { cin >> e; for (int i = 1; i * i < e + 1; i++) { if (e % i == 0) { B[i]++; if (i * i != e) B[e / i]++; } } } vector<int> res(N, 1); for (int i = 0; i < (int)B.size(); i++) { if (B[i] > 0) { res[N - B[i]] = max(res[N - B[i]], i); } } for (int i = 0; i + 1 < N; i++) { res[i + 1] = max(res[i + 1], res[i]); } for (const auto& e : res) { cout << e << '\n'; } return 0; }