結果
問題 | No.2570 最大最大公約数 |
ユーザー |
![]() |
提出日時 | 2023-12-02 16:10:05 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 332 ms / 2,000 ms |
コード長 | 6,922 bytes |
コンパイル時間 | 3,106 ms |
コンパイル使用メモリ | 231,404 KB |
最終ジャッジ日時 | 2025-02-18 05:14:41 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
// Enjoy your stay. Code by evima#include <atcoder/modint>#include <atcoder/segtree>using namespace atcoder;using mint = modint998244353; // modint;#include <bits/stdc++.h>using namespace std;using ld = long double;using ll = long long;using lll = __int128;using pl = pair<ll, ll>;using vl = vector<ll>;using vm = vector<mint>;using vp = vector<pl>;using vs = vector<string>;using vvl = vector<vl>;using LOOPVAR_TYPE = ll;#define all(x) (x).begin(), (x).end()#define mset(a, v) memset(a, v, sizeof(a))#define sq(x) ((x) * (x))#define sz(x) ll((x).size())#define GET_MACRO(_1, _2, _3, _4, NAME, ...) NAME#define rep1(i, n) rep2(i, 0, n)#define rep2(i, a, b) \for (LOOPVAR_TYPE i = LOOPVAR_TYPE(a); i < LOOPVAR_TYPE(b); i++)#define rep3(i, a, b, c) \for (LOOPVAR_TYPE i = LOOPVAR_TYPE(a); \(c) > 0 ? i < LOOPVAR_TYPE(b) : i > LOOPVAR_TYPE(b); i += (c))#define rep(...) GET_MACRO(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)#define eb emplace_back#define fir first#define sec second#define mp make_pair#define mt make_tupleconst int PREC = 20;const ld EPS = 1e-9;const ld PI = 3.14159265358979323846L;const ll INF = 1070000000LL;const ll MOD = 998244353LL; // 1000000007LL;const ll inf = 2.07e18;const string IMPOSSIBLE = "IMPOSSIBLE";const string POSSIBLE = "POSSIBLE";void fast_io() {cin.tie(NULL);ios_base::sync_with_stdio(false);}ll lin() {ll x;cin >> x;return x;}string input() {string s;cin >> s;return s;}vl vin(int n) {vl v(n);rep(i, n) cin >> v[i];return v;}vs vsin(int n) {vs v(n);rep(i, n) cin >> v[i];return v;}vvl vvin(int n, int m) {vvl w(n, vl(m));rep(i, n) rep(j, m) cin >> w[i][j];return w;}vvl vvin(int n) { return vvin(n, n); }template <typename T>vector<T> cat(vector<T> v, const vector<T>& w) {for (T x : w) v.eb(x);return v;}template <typename T>bool chmin(T& a, const T& b) {return (b < a) ? (a = b, true) : false;}template <typename T>bool chmax(T& a, const T& b) {return (a < b) ? (a = b, true) : false;}template <typename T>map<T, ll> freq(const vector<T>& v) {map<T, ll> ret;for (T x : v) ++ret[x];return ret;}template <typename T>vector<T> reversed(vector<T> v) {reverse(all(v));return v;}template <typename T>vector<T> sorted(vector<T> v) {sort(all(v));return v;}template <typename T>vector<T> sub(const vector<T>& v, int from, int to) {vector<T> ret;copy(&v[from], &v[to], back_inserter(ret));return ret;}template <typename T>string str(const T& x) {stringstream ss;ss << setprecision(PREC);ss << x;return ss.str();}string str(const mint& x) { return str(x.val()); }template <typename Tuple, size_t... I>array<int, sizeof...(I)> str_tuple_impl(stringstream& ss, Tuple&& t,index_sequence<I...>) {return {{(void(ss << str(get<I>(t)) << " "), 0)...}};}template <typename Tuple>string str_tuple(Tuple&& t) {stringstream ss;ss << setprecision(PREC);str_tuple_impl(ss, forward<Tuple>(t),make_index_sequence<tuple_size<decay_t<Tuple>>::value>{});string s = ss.str();if (s.size() > 0) s.pop_back();return s;}template <typename T, typename U>string str(const pair<T, U>& p) {return str_tuple(p);}template <typename... T>string str(const tuple<T...>& t) {return str_tuple(t);}template <typename T>string str(const vector<T>& v) {stringstream ss;ss << setprecision(PREC);rep(i, sz(v)) ss << str(v[i]) << (i < sz(v) - 1 ? " " : "");return ss.str();}template <typename T>T sum(const vector<T>& v) {return accumulate(all(v), 0LL);}template <typename T>vector<vector<T>> trans(const vector<vector<T>>& w) {int n = sz(w), m = sz(w[0]);vector<vector<T>> ret(m, vector<T>(n));rep(i, m) rep(j, n) ret[i][j] = w[j][i];return ret;}vector<string> trans(const vector<string>& w) {int n = sz(w), m = sz(w[0]);vector<string> ret(m, string(n, ' '));rep(i, m) rep(j, n) ret[i][j] = w[j][i];return ret;}template <typename T>void print1(T&& x, const string& end) {cout << str(x) << end;}void pr() { print1("", ""); }template <typename T, typename... U>void pr(T&& head, U&&... tail) {print1(head, "");pr(forward<U>(tail)...);}void print() { print1("", "\n"); }template <typename T, typename... U>void print(T&& head, U&&... tail) {print1(head, " ");print(forward<U>(tail)...);}template <typename T>void eprint1(T&& x, const string& end) {cerr << str(x) << end;}void eprint() { eprint1("", "\n"); }template <typename T, typename... U>void eprint(T&& head, U&&... tail) {eprint1(head, " ");eprint(forward<U>(tail)...);}template <typename... T>void quit(T&&... x) {print(forward<T>(x)...);exit(0);}void yn(bool cnd) {if (cnd)print("Yes");elseprint("No");}template <typename T, typename U>void yn(bool cnd, T&& yes, U&& no) {if (cnd)print(yes);elseprint(no);}void zip(vl& v) {vl w = v;sort(all(w));int n = unique(all(w)) - w.begin();for (ll& x : v) x = lower_bound(&w[0], &w[n], x) - &w[0];}vl zipped(vl v) {zip(v);return v;}map<ll, ll> zipmap(vl v) {map<ll, ll> ret;sort(all(v));v.erase(unique(all(v)), v.end());rep(i, sz(v)) ret[v[i]] = i;return ret;}void init(){};int N;vector<vector<pair<int, ll>>> g, gr;vl bfs(int s, int r = 0){vl dist(N, inf);priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;q.push({0, s});dist[s] = 0;while(!q.empty()){auto [c, v] = q.top(); q.pop();if(dist[v] < c) continue;for(auto& [u, t] : (r == 0 ? g : gr)[v]){ll nd = dist[v] + t;if(nd < dist[u]) {dist[u] = nd;q.push({nd, u});}}}return dist;}unordered_set<ll> s;void div(ll N){for(ll i = 1; i * i <= N; ++i){if(N % i == 0){s.insert(i);if(i * i != N) s.insert(N / i);}}//return ret;}void solveOne() {int N, K;cin >> N >> K;vl A(N);rep(i, N) {cin >> A[i];div(A[i]);}vl v;for(ll x: s) v.eb(x);sort(all(v));reverse(all(v));for(ll x: v){ll cnt = 0;bool ok = 1;for(ll y: A){ll d = min(y % x, x - y % x);cnt += d;if(cnt > K) { ok = 0; break; }}if(ok){print(x);return;}}}int main() {int T=1;//cin >> T;init();rep(i, 1, T + 1) {//cout << "Case #" << i << ": ";solveOne();}}