C - Maximize GCD

給定長度為$n,(2\le 3\times 10^5)$的數(shù)組$a,(1\le a_i\le 3\times 10^5)$，一個數(shù)字$K,(1\le K\le 10^{18})$，

我們可以對數(shù)組$a$進(jìn)行最多$k$次操作，每次操作選定一個$i,(1\le i\le n)$使$a_i+1$，為數(shù)組最大的可能$gcd$是多少。

我們設(shè)$maxn=max(\{a_1,\dots ,a_n\})$，如果最后的答案$ans$大于等于$maxn$，則一定有$i\in [1,n],a_i=ans$。

否則我們假設(shè)答案為$x$，則判斷是否合法：
$$\sum _{i=1}^n?\frac{a_i}{x}?\times x?a_i$$
即上面那個式子求和是否小于等于$k$，這個式子可以前綴和，無窮級數(shù)的復(fù)雜度算一下就好了，整體復(fù)雜度最高$maxn\log maxn$。

#include <bits/stdc++.h>using namespace std;const int N = 3e5 + 10;int a[N], cnt[N], n, maxn;long long sum[N], k, s;int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);cin >> n >> k;for (int i = 1; i <= n; i++) {cin >> a[i];s += a[i], cnt[a[i]]++, sum[a[i]] += a[i];maxn = max(maxn, a[i]);}if (1ll * maxn * n - s <= k) {// x * n - sum <= k -> x * n <= k + sum -> x = (k + sum) / n;cout << (k + s) / n << "\n";return 0;}for (int i = 1; i <= maxn; i++) {cnt[i] += cnt[i - 1];sum[i] += sum[i - 1];}int ans = 1;for (int i = 2; i < maxn; i++) {long long cur = 0;for (int j = i; j <= maxn; j += i) {// [j - i + 1, j] -> icur += 1ll * (cnt[j] - cnt[j - i]) * j - (sum[j] - sum[j - i]);}if (maxn % i) {int l = maxn / i * i, r = maxn;cur += 1ll * (cnt[r] - cnt[l]) * (maxn / i + 1) * i - (sum[r] - sum[l]);}if (cur <= k) {ans = i;}}cout << ans << "\n";return 0; }

總結(jié)

以上是生活随笔為你收集整理的C - Maximize GCD（简单数论）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。