結果
問題 | No.2570 最大最大公約数 |
ユーザー |
|
提出日時 | 2023-12-06 02:13:56 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 333 ms / 2,000 ms |
コード長 | 1,781 bytes |
コンパイル時間 | 1,595 ms |
コンパイル使用メモリ | 133,388 KB |
最終ジャッジ日時 | 2025-02-18 08:15:05 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
/* 💕💕💕💕💕💗💗💗💗💗/)/)( . .)( づ💗💗💗💗 💗💗💗💗💗💗💗💗💗💗💗💗💗💗💗💗💗💗💗💗💗💗💗💗💗💗💗💗💗💗💗💗💗💗💗💗💗*/#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <chrono>#include <cmath>#include <complex>#include <cstdint>#include <cstring>#include <ctime>#include <deque>#include <iomanip>#include <iostream>#include <map>#include <numeric>#include <queue>#include <random>#include <set>#include <stack>#include <unordered_map>#include <unordered_set>#include <vector>void solve() {long long n, k;std::cin >> n >> k;std::vector<long long> a(n);for (auto& i : a) std::cin >> i;auto get_divisors = [](long long n) {std::vector<long long> res;for (long long i = 1; i * i <= n; i++) {if (n % i == 0) {res.push_back(i);if (i * i != n) res.push_back(n / i);}}return res;};std::set<long long, std::greater<long long>> c;for (int i = 0; i < n; i++) {auto p = get_divisors(a[i]);for (auto j : p) {c.insert(j);}}for (auto g : c) {long long cnt = 0;for (auto x : a) {long long distance = std::abs(g * (x / g + 1) - x);if (x > g) distance = std::min(distance, x % g);if (x == distance) distance = 0;cnt += distance;// if (g == 998244353) std::cout << distance << '\n';}if (cnt <= k) {std::cout << g << '\n';return;}}std::cout << 1 << '\n';}int main() {int t = 1;std::ios::sync_with_stdio(false);std::cin.tie(nullptr);// std::cin >> t;while (t--) solve();return 0;}