結果
問題 | No.2570 最大最大公約数 |
ユーザー |
|
提出日時 | 2023-12-02 16:35:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 48 ms / 2,000 ms |
コード長 | 2,579 bytes |
コンパイル時間 | 2,453 ms |
コンパイル使用メモリ | 204,944 KB |
最終ジャッジ日時 | 2025-02-18 05:31:47 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h>using namespace std;template <typename T> using min_priority_queue = priority_queue<T,vector<T>,greater<T>>;template<typename T>void printv(vector<T> &v){bool b = false;for(auto i : v){if(b) cout << " ";else b = true;cout << i;}cout << endl;}template <typename T>bool chmin(T &a, const T& b) {if (a > b) {a = b; // aをbで更新return true;}return false;}template <typename T>bool chmax(T &a, const T& b) {if (a < b) {a = b; // aをbで更新return true;}return false;}void yn(bool b){if(b) cout << "Yes" << endl;else cout << "No" << endl;}bool debug;bool randomInput;void input(){if(debug && randomInput){}else{}return;}void calc(){int N, K;cin >> N >> K;vector<int64_t> A(N);for(int i = 0; i < N; i++){cin >> A[i];}vector<vector<int64_t>> D;int sz = 0;for(int i = 0; i < N; i++){for(int j = i+1; j < N; j++){int64_t d = abs(A[i] - A[j]);if(d <= K) continue;D.push_back({});sz++;for(int k = 0; k <= K; k++){D[sz-1].push_back(d-k);}}}set<int64_t> S;if(D.size()){for(int64_t j : D[0]){for(int64_t k = 1; k*k <= j; k++){if(j%k == 0){S.insert(k);S.insert(j/k);}}}}else{int64_t Amin = 1001002003004005006;int64_t Amax = 0;for(int64_t i : A){chmin(Amin, i);chmax(Amax, i);}for(int64_t i = 1; i <= 2*K; i++){S.insert(i);}for(int64_t i = Amin; i <= Amax; i++){S.insert(i);}}int64_t ans = 0;for(int64_t i : S){int64_t cnt = 0;for(int64_t j : A){cnt += min(j%i, (i-j%i)%i);}if(cnt > K) continue;chmax(ans, i);}cout << ans << endl;return;}int64_t ansSimple;void calcSimple(){return;}void calc1(){int t; cin >> t;for(int i = 0; i < t; i++){input();calc();calcSimple();}}int main(){debug = 0;randomInput = 0;srand(time(NULL));cout << fixed << setprecision(12);if(debug){calc1();}else{input();calc();}return 0;}//