結果
問題 | No.2570 最大最大公約数 |
ユーザー |
|
提出日時 | 2023-12-06 02:12:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 41 ms / 2,000 ms |
コード長 | 1,879 bytes |
コンパイル時間 | 1,654 ms |
コンパイル使用メモリ | 133,764 KB |
最終ジャッジ日時 | 2025-02-18 08:14:58 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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 prime_factor = [](long long x) {std::vector<long long> res;for (long long i = 2; i * i <= x; ++i) {if (x % i == 0) {res.push_back(i);while (x % i == 0) x /= i;}}if (x != 1) res.push_back(x);return res;};std::set<long long, std::greater<long long>> c;for (int i = 0; i < n; i++) {c.insert(a[i]);auto p = prime_factor(a[i]);for (auto j : p) {c.insert(j);}}for (int x = 2; x <= 10; x++) {c.insert(x);}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;}