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

Упорядочим числа 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;46;2352);(2;23;650);(3;16;342);(4;12;210);(5;10;156);(6;8;110);(7;8;110);(8;9;132);(9;10;156);(10;11;182))\text{таблица}=\left(\left(1;46;2352\right);\left(2;23;650\right);\left(3;16;342\right);\left(4;12;210\right);\left(5;10;156\right);\left(6;8;110\right);\left(7;8;110\right);\left(8;9;132\right);\left(9;10;156\right);\left(10;11;182\right)\right)

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

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

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