Проверка количества по двум крайним произведениям

Упорядочим числа a1<…<aka_{1}<\ldots<ak. Условия для всех пар равносильны a1a2>La_{1}a_{2}>L и ak−1ak<Ua_{k-1}a_{k}<U. При фиксированном a1=xa_{1}=x наименьшее допустимое второе число y=max⁡(x+1, ⌊Lx⌋+1)y=\max\left(x+1,\,\left\lfloor \frac{L}{x}\right\rfloor +1\right); остальные выбираем y+1, …, y+k−2y+1,\,\ldots,\,y+k-2. Это минимизирует наибольшее произведение, поэтому если даже оно не меньше UU, других наборов с таким xx нет. Достаточно 1≤x≤⌊U−1⌋1\leq x\leq\left\lfloor \sqrt{U-1}\right\rfloor, поскольку x2<a1a2<Ux^{2}<a_{1}a_{2}<U. В таблице указаны xx, yy и минимальное наибольшее произведение; подходящая строка даёт пример.

Учебный авторский материал. Порядок изучения не означает новую экспертную проверку решения или проверку источников.

Что нужно знать

Применение в задаче

Шаг 1. Упорядочим числа a1<…<aka_{1}<\ldots<ak. Условия для всех пар равносильны a1a2>La_{1}a_{2}>L и ak−1ak<Ua_{k-1}a_{k}<U. При фиксированном a1=xa_{1}=x наименьшее допустимое второе число y=max⁡(x+1, ⌊Lx⌋+1)y=\max\left(x+1,\,\left\lfloor \frac{L}{x}\right\rfloor +1\right); остальные выбираем y+1, …, y+k−2y+1,\,\ldots,\,y+k-2. Это минимизирует наибольшее произведение, поэтому если даже оно не меньше UU, других наборов с таким xx нет. Достаточно 1≤x≤⌊U−1⌋1\leq x\leq\left\lfloor \sqrt{U-1}\right\rfloor, поскольку x2<a1a2<Ux^{2}<a_{1}a_{2}<U. В таблице указаны xx, yy и минимальное наибольшее произведение; подходящая строка даёт пример.
таблица=((1;26;812);(2;13;240);(3;9;132);(4;7;90);(5;6;72);(6;7;90);(7;8;110);(8;9;132);(9;10;156))\text{таблица}=\left(\left(1;26;812\right);\left(2;13;240\right);\left(3;9;132\right);\left(4;7;90\right);\left(5;6;72\right);\left(6;7;90\right);\left(7;8;110\right);\left(8;9;132\right);\left(9;10;156\right)\right)

Всё решение и условие задачи Решить задачу

Следующий шаг

Задачи по этому методу