Вопрос очень простой, но интересный. Эта статья продемонстрирует вам вопрос от Codeforces о сжатии GCD[Greatest common divisor]. Ссылка на вопрос здесь: -
Согласно условиям задачи вам дан массив A длины 2N (вам дано N). вы создали новый массив B длины (N-1), так что GCD всех его элементов должен быть больше единицы.
пример:- gcd(b1,b2…,bn−1)›1.
давайте вспомним некоторые основы математики, если вы добавите два нечетных целых числа, их сумма всегда будет четной, а если вы добавите два четных целых числа, то некоторые из них также будут четными. Итак, если мы поместим все четные элементы в массив B, то их НОД всегда ≥2, что удовлетворяет наши условия.
Итак, нам нужно подсчитать общее количество нечетных и четных целых чисел в массиве.
Num(нечетное) + Num(четное) = 2N, где Num(x) — количество элементов типа x.
Мы знаем, что есть четные числа с правой стороны. Тогда есть две возможности.
[I] : Num(нечетное) и Num(четное) четные.
OR
[II] : Num(нечетное) и Num(четное) оба нечетные.
Возьмем случай [I]: -
[I] : Num(нечетное) и Num(четное) четные.
Сначала вам нужно удалить два элемента либо из Num (нечетных), либо из Num (четных) элементов. Затем в массиве B у нас есть элементы Num(нечетные) [В паре (поэтому сумма кратна двум)], а после этого Num(четные)[В паре].
Теперь давайте обсудим случай [II]: -
[II] : Num(нечетное) и Num(четное) оба нечетные.
В этом случае вам нужно удалить одно целое число как из Num (четное), так и из Num (нечетное). Итак, теперь ваши Num (нечетное) и Num (четное) стали четными. как в первом случае. Теперь сделайте то же самое. В массиве B у нас есть элементы Num(нечетные) [в паре (так что сумма кратна двум)], а после этого Num(четные)[в паре].
Вот ссылка кода на С++: -
"Решение"
Я надеюсь, что вы понимаете это объяснение и надеюсь увидеть вас в ближайшее время.
