| Автор: | Центральная предметно-методическая комиссия | Ограничение времени: | 1 сек | |
| Входной файл: | Стандартный вход | Ограничение памяти: | 512 Мб | |
| Выходной файл: | Стандартный выход | |||
| Максимальный балл: | 100 |
Учёные планируют участок для испытательного полигона. Участок должен иметь форму прямоугольника a × b, а полигон должен иметь форму прямоугольника c × d. С точными значениями чисел a, b, c и d ученые пока не определились, однако известно следующее:
Учёные хотят понять, сколько у них способов выбрать подходящие значения a, b, c и d.
Требуется написать программу, которая по заданным n и x определяет количество способов выбрать числа a, b, c и d так, чтобы все описанные условия выполнялись.
В первой строке ввода содержится два целых числа n и x — площадь свободного участка без полигона и запрещенная длина стороны участка соответственно.
Значение x = 0 означает, что ограничений на длины сторон нет (так как длины сторон должны быть натуральными числами, и, следовательно, больше 0).
В единственной строке выведите количество способов выбрать числа a, b, c и d так, что все описанные условия выполняются.
1 ≤ n ≤ 3000
0 ≤ x ≤ 3000
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
|---|---|---|---|---|
| 1 | 11 | 1 ≤ n ≤ 50, x = 0 | первая ошибка | |
| 2 | 10 | 1 ≤ n ≤ 50 | 1 | первая ошибка |
| 3 | 20 | 1 ≤ n ≤ 500, x = 0 | 1 | баллы |
| 4 | 22 | 1 ≤ n ≤ 500 | 1, 2, 3 | баллы |
| 5 | 17 | 1 ≤ n ≤ 3000, x = 0 | 1, 3 | баллы |
| 6 | 20 | 1 ≤ n ≤ 3000 | 1, 2, 3, 4, 5 | баллы |
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|
| 2 | |
|
| 3 | |
|
Заметим, что если a > n, то ab − cd > ab − ad = a(b − d) > a > n и никакие значения b, c и d не подходят. Следовательно a n. Аналогично доказывается, что b ≤ n.
Переберём a и b от 2 до n,а также c от 1 до a − 1 и d от 1 до b − 1. Проверив для каждого варианта,что ab − cd = n, получим решение первой подзадачи за O(n4), которое несложно модифицируется, чтобы убеждаться, что a ≠ x и b ≠ x, тем самым решая подзадачу 2.
Пусть мы зафиксировали a, b и c. Тогда заметим, что d определяется единственным образом из уравнения ab − cd = n: если ab − n кратно c, то d = (ab − n) / c, иначе никакие значения d не подходят. Следует также не забыть проверить, что 1 ≤ d < b. Получаем решение за O(n3), оно подходит для подзадачи 3, а добавляя проверки a ≠ x и b ≠ x, также и для подзадачи 4.
Для решения подзадачи 5 можно применить забавный трюк. Давайте подсчитаем предыдущим алгоритмом за O(n3) решения для всех возможных значений n. Решение за O(n4) работает очень долго для n порядка 3000, но у нас почти все время тура. Все полученные значения поместим в константный массив. Такой метод известен как предподсчёт. К сожалению, сделать предподсчёт для шестой подзадачи не получается, это и слишком долго, и занимает слишком много места, такой большой исходный файл не удастся отправить на проверку.
Наконец, решение за O(n2logn), которое решает задачу полностью. Вместо c будем перебирать a − c. Заметим, что ab − cd = ab − bc + bc − cd = (a − c) ⋅ b + c ⋅ (b − d). Поскольку c > 0 и b > d, второе слагаемое положительно, и следовательно (a − c) ⋅ b < n. Таким образом, достаточно перебирать только O(n / b) значений. Значит для каждого a будет перебираться n + n / 2 + n / 3 + ... + n / n = n(1 + 1 / 2 + 1 / 3 + ... + 1 / n) пар значений. Cумма 1 + 1 / 2 + 1 / 3 + ... + 1 / n хорошо известна—это частичная сумма гармонического ряда, она равна O(logn), следовательно суммарно для фиксированного a перебирается O(nlogn) значений, а общее время работы алгоритма равно O(n2logn). Финальное замечание, что так как a и b перебираются явно, нет проблемы убедиться, что a ≠ x и b ≠ x.