Задание 27: Программирование

Типичная формулировка: дана последовательность чисел или пар чисел (до $6\cdot10^4$–$10^5$ элементов), нужно вычислить сумму/произведение/количество пар, удовлетворяющих условию делимости или максимальности при ограничении. Входные данные — два файла: А (маленький, можно решить и перебором) и B (большой, переборный алгоритм не успеет отработать). В ответе указываются два числа — результат для файла А и для файла B, в этом порядке. За задание дают 2 балла: по одному за каждый файл, если программа выдаёт верный ответ и использует принципиально верный (не экспоненциальный) алгоритм. Достаточно пр …

• Остаток от деления: $a \bmod m$ — число от $0$ до $m-1$, такое что $a = qm + (a\bmod m)$.
• Делимость: $a$ делится на $b$ тогда и только тогда, когда $a \bmod b = 0$.
• Разложение модуля на простые множители — ключ к решению: $14 = 2\cdot 7$, $26 = 2\cdot 13$.
• Произведение $x\cdot y$ делится на $p\cdot q$ (простые $p\ne q$), если множители $p$ и $q$ в сумме «набираются» у $x$ и $y$: одно число делится на $pq$, либо одно делится на $p$, другое — на $q$.
• Число пар внутри одной группы размера $k$: $\binom{k}{2} = \dfrac{k(k-1)}{2}$.
• Число пар между двумя разными группами размерами $k$ и $l$: $k\cdot l$.
• Сложность: полный перебор пар — $O(n^2)$, при $n=10^5$ это $10^{10}$ операций (слишком долго); проход с группировкой — $O(n)$ или $O(n\log n)$.
• При $n\le 10^5$ и элементах до $10^4$ сумма может достигать $10^9$, произведение — до $10^8$; в C++/Pascal нужен 64-битный тип, в Python переполнения нет.

1. Прочитать входные данные: количество элементов $N$ и сами значения.
2. Определить признак, связанный с условием (остаток от деления или простые множители модуля из условия).
3. Завести переменные-агрегаты для каждого кластера (количество, сумма, максимум, топ-несколько значений).
4. Один раз пройти по элементам, распределяя каждый в соответствующий кластер и обновляя агрегаты.
5. По собранным агрегатам применить формулу задачи (суммирование, $k\cdot l$, $\binom{k}{2}$, минимальная коррекция, перебор top-k) — без обращения ко всему массиву.
6. Повторить для обоих файлов (маленький можно проверить и перебором) и вывести оба числа в требуемом порядке.