logoChat01.ai

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

Tạo vào: 24 tháng 10, 2025

Trả lời bằng GPT-5 Thinking bởi Chat01

Câu hỏi

Вам дано целое число 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++

Suy nghĩ

Solving GCD maximization

The problem requires maximizing the GCD after performing up to k erasures and using "split" operations. By splitting a number into three parts, we remove one part, keeping only two numbers. This alters the sum, but we focus on maximizing GCD. Effective splits might adjust residues modulo d to help maximize the GCD.

Maximizing GCD with modifications

To maximize the GCD, the task is to find a number d such that the remaining numbers are all divisible by d. The key operation is splitting a number into parts, potentially removing elements that don't fit. We have to experiment with splits to make sure each number becomes divisible by d, and deletions can help too.

Testing possible splits

For the split operation, the goal is to discard one part while ensuring the two remaining parts are divisible by d. If we set x1 and x3 as multiples of d, we want to check if it's possible for x2 to discard any remainder. This depends on the values and constraints of x1, x2, and x3.

Finding feasible splits

To make the split work, I need to ensure x2 is divisible by d, and I want x1 ≤ x2 ≤ x3. I choose x1 and x3 as multiples of d and set x2 as the remainder. After some calculations, I see that x needs to satisfy x = 3d for the split to be possible.

Exploring splits and constraints

Let's refine our approach. If x is greater than or equal to 3d, I can split x into multiples of d. However, for x less than 3d, it's tricky. We can break numbers into smaller parts, but they can't become multiples of d through splitting operations alone unless x is large enough.

Refining splits and conditions

To transform any x ≥ 3d into multiples of d, we need to adjust our splits. When x is a sum of multiples, the condition is that x must be divisible by d or, for larger numbers, split to be. The challenge lies in ensuring the monotonic order and calculating when splits will maintain multiples of d without breaking the constraints.

Verifying splits and bounds

I’m refining the conditions for splitting x into multiples of d. Specifically, I'll focus on calculating when a split produces numbers greater than or equal to 3d, as smaller numbers cannot satisfy the constraints. I’ll ensure the correct balance between lower and upper bounds, testing various cases for different q values.

Analyzing erasures and splits

I'm refining the process for splitting numbers into multiples of d, trying to minimize the number of erasures needed. If an x isn't already a multiple or can't be split into multiples, I may need to erase parts, especially when the leftover residue is too small. The goal is to optimize the splits and deletions.

Analyzing minimal erasures

I’m working through how to minimize the number of erasures needed to transform numbers into multiples of d. For some x, splitting alone isn’t enough, and an erasure may be necessary. Specifically, for numbers in certain ranges, converting them requires 1 erasure. However, numbers larger than 4d can be split into valid multiples without erasures.

Finding conditions for no erasures

I’m working through the conditions under which no erasures are necessary. The key point is that a number is only bad if it’s less than 4d and not divisible by d. The goal is to find how many such bad numbers there are, and ensure that k (the maximum number of bad numbers we’re allowed to erase) doesn’t exceed this count. Then, we check if there's at least one "good" element remaining for each choice of d.

Confirming reach of gcd condition

It's important to ensure that the number of "bad" elements doesn't exceed k and that at least one "good" element remains. If there's a feasible d, we compute the "bad" count. The algorithm checks the relevant bounds and uses prefix sums to determine the maximum d where the gcd condition holds.

Confirming algorithm logic and constraints

The algorithm appears sound. I need to handle edge cases, ensuring bounds don't result in negative counts (e.g., for large d or small n). It’s clear that the formula for counting "bad" values holds even when dealing with large inputs. Now, it’s important to implement a Python check for smaller cases and manage conflicts with variable names carefully.

Finalizing algorithm and edge cases

The algorithm looks solid, but handling edge cases is crucial. I’ve confirmed that for each test, constructs like prefix and count arrays are in place. Cases with numbers exceeding allowed limits (like ai > n) are invalid, so streamlining input validation will help. The edge cases are well-tested too—such as cases where values are right

Thought for 3m 38s

Trả lời

Идея:

Пусть хотим добиться НОД = d. Тогда каждый оставшийся элемент должен стать кратным d. Операция «Разделить» позволяет для любого x≥4dx \ge 4d за один шаг заменить xx на два числа, оба кратные dd (конструктивно можно взять x1=d, x3=⌈⌊x/d⌋2⌉dx_1=d,\ x_3 = \lceil \frac{\lfloor x/d\rfloor}{2}\rceil d, тогда порядок x1≤x2≤x3x_1\le x_2\le x_3 выполним, а оба сохраняемых — кратны dd).
Если же x<4dx < 4d и x≢0(modd)x \not\equiv 0 \pmod d, превратить его в набор, целиком кратный dd, невозможно без удаления — придётся стереть такой элемент.

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

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

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

Ответ — максимальное dd с bad(d)≤kbad(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)O(n) по суммарному ограничению ∑n≤2⋅105\sum n \le 2\cdot10^5.

Chia sẻ Q&A này