結果
問題 | No.2570 最大最大公約数 |
ユーザー |
|
提出日時 | 2023-12-02 16:01:48 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,184 ms / 2,000 ms |
コード長 | 1,697 bytes |
コンパイル時間 | 4,282 ms |
コンパイル使用メモリ | 251,184 KB |
最終ジャッジ日時 | 2025-02-18 05:08:35 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;struct Fast {Fast() {std::cin.tie(nullptr);ios::sync_with_stdio(false);cout << setprecision(10);}} fast;#define all(a) (a).begin(), (a).end()#define contains(a, x) ((a).find(x) != (a).end())#define rep(i, a, b) for (int i = (a); i < (int)(b); i++)#define rrep(i, a, b) for (int i = (int)(b)-1; i >= (a); i--)#define YN(b) cout << ((b) ? "YES" : "NO") << "\n";#define Yn(b) cout << ((b) ? "Yes" : "No") << "\n";#define yn(b) cout << ((b) ? "yes" : "no") << "\n";template <typename T>ostream& operator<<(ostream& os, vector<T>& vec) {for (int i = 0; i < vec.size(); i++) {os << vec[i] << (i + 1 == vec.size() ? "" : " ");}return os;}using ll = long long;using vb = vector<bool>;using vvb = vector<vb>;using vi = vector<int>;using vvi = vector<vi>;using vl = vector<ll>;using vvl = vector<vl>;using mint = modint998244353;using vm = vector<mint>;using vvm = vector<vm>;inline ostream& operator<<(ostream& os, const mint P) { return os << P.val(); };void solve() {int n, k;cin >> n >> k;vl a(n);rep(i, 0, n) cin >> a[i];ll ans = 1;for (ll g = 2; g <= 1e6; g++) {ll c = 0;rep(i, 0, n) {ll v = a[i] / g * g;c += min(a[i] - v, v + g - a[i]);}if (c <= k) ans = g;}rep(i, 0, n) rep(j, -k, k + 1) {if (a[i] + j <= 0) continue;ll g = a[i] + j;ll c = 0;rep(i, 0, n) {ll v = a[i] / g * g;c += min(a[i] - v, v + g - a[i]);}if (c <= k) ans = max(ans, g);}cout << ans << "\n";}int main() {int t = 1;// cin >> t;while (t--) solve();}