Вам дано целое число k и n целых положительных ч...

Question

Вам дано целое число k
и n
целых положительных чисел a1,a2,…,an
, записанных на доске, где 1≤ai≤n
. Вы можете выполнять следующие операции:

Стереть: Выберите целое число с доски и сотрите его. Эту операцию можно выполнить не более k
раз.
Разделить: Выберите целое число x≥3
с доски. Разделите его на три целых положительных числа x1
, x2
и x3
так, чтобы выполнялось x1+x2+x3=x
и 1≤x1≤x2≤x3
. Затем сотрите x
с доски и запишите два новых числа x1
и x3
на доске. Обратите внимание, что x2
отбрасывается и не записывается на доске. Эту операцию можно выполнять любое количество раз.
Красота коллекции целых чисел b
определяется как наибольший общий делитель всех элементов в b
. Формально, это наибольшее целое число d
, такое что d
делит x
для каждого x
, который является элементом b
.

Ваша задача — определить максимальную возможную красоту чисел на доске после выполнения не более k
операций Стереть и любого количества операций Разделить.

Входные данные
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число t
(1≤t≤104
) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа n
и k
(1≤n≤2⋅105
, 0≤k≤n−1
) — количество чисел на доске и максимальное количество разрешенных операций Стереть.

Вторая строка каждого набора входных данных содержит n
целых чисел a1,a2,…,an
(1≤ai≤n
) — числа, изначально записанные на доске.

Гарантируется, что сумма значений n
по всем наборам входных данных не превосходит 2⋅105
.

Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальную красоту элементов, записанных на доске после выполнения операций.
c++

Answer 1

Идея:

Пусть хотим добиться НОД = d. Тогда каждый оставшийся элемент должен стать кратным d. Операция «Разделить» позволяет для любого $x \ge 4d$ за один шаг заменить $x$ на два числа, оба кратные $d$ (конструктивно можно взять $x_1=d,\ x_3 = \lceil \frac{\lfloor x/d\rfloor}{2}\rceil d$ , тогда порядок $x_1\le x_2\le x_3$ выполним, а оба сохраняемых — кратны $d$ ).
Если же $x < 4d$ и $x \not\equiv 0 \pmod d$ , превратить его в набор, целиком кратный $d$ , невозможно без удаления — придётся стереть такой элемент.

Значит, для фиксированного $d$ «плохие» элементы — это те, у которых $a_i < 4d$ и $a_i \not\equiv 0 \pmod d$ . Если их число $\le k$ , то можем их стереть, остальные либо уже кратны $d$ , либо $\ge 4d$ и приводятся разбиениями к кратным $d$ . Нужно максимизировать $d$ .

Подсчёт для каждого $d$ делается за $O(1)$ с префикс-суммами по частотам:
число $a_i < 4d$ равно $pref[\min(n,4d-1)]$ , из них «хорошие» кратные — это только значения $d,2d,3d$ (если они $\le n$ ). Тогда

bad(d)=pref[\min(n,4d-1)] - \big(cnt[d]+cnt[2d]+cnt[3d]\big).

Ответ — максимальное $d$ с $bad(d)\le k$ .

Вот реализация.

cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        int n, k;
        cin >> n >> k;
        vector<int> cnt(n + 1, 0);
        for (int i = 0; i < n; ++i) {
            int x; cin >> x;
            ++cnt[x];
        }
        vector<int> pref(n + 1, 0);
        for (int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + cnt[i];

        int ans = 1;
        for (int d = 1; d <= n; ++d) {
            int bound = min(n, 4 * d - 1);
            int num_lt4d = pref[bound];

            int good_div = 0;
            if (d <= n) good_div += cnt[d];
            if (2 * d <= n) good_div += cnt[2 * d];
            if (3 * d <= n) good_div += cnt[3 * d];

            int bad = num_lt4d - good_div;
            if (bad <= k) ans = d;
        }
        cout << ans << '\n';
    }
    return 0;
}

Сложность: для каждого теста $O(n)$ по суммарному ограничению $\sum n \le 2\cdot10^5$ .

Вам дано целое число k и n целых положительных ч...

問題

思考

Solving GCD maximization

Maximizing GCD with modifications

Testing possible splits

Finding feasible splits

Exploring splits and constraints

Refining splits and conditions

Verifying splits and bounds

Analyzing erasures and splits

Analyzing minimal erasures

Finding conditions for no erasures

Confirming reach of gcd condition

Confirming algorithm logic and constraints

Finalizing algorithm and edge cases

回答

分享這個問答