Условие
Для прямоугольной клумбы доступно не более s квадратных метров земли и не более p метров ограждения. Стороны a и b — положительные целые числа. Требуется ab ≤ s и 2(a + b) ≤ p. Прямоугольники, совпадающие после поворота, считаются одинаковыми: a × b и b × a — один размер. Найдите число различных подходящих размеров.
Входные данные
В первой строке целое s (1 ≤ s ≤ 10^12), во второй — целое p (4 ≤ p ≤ 10^12). Ответ может превышать 32-битный целый тип.
Что вывести
Выведите одно целое число — ответ на задачу.
Как понимать условие
Использовать всю землю и всё ограждение необязательно. При s = 6 и p = 10 клумба 2×3 подходит: площадь равна 6, периметр — 10. Клумба 1×4 тоже подходит: площадь равна 4, периметр — 10. А размер 1×5 уже не подходит из-за периметра 12. Поворот 3×2 не создаёт нового размера. Нужно посчитать все допустимые пары сторон, а не найти наибольшую площадь.
Как убрать повороты из подсчёта
При s = 6 и p = 10 подходят размеры 1×1, 1×2, 1×3, 1×4, 2×2 и 2×3. Размер 3×2 повторяет 2×3. Чтобы каждый прямоугольник учитывать один раз, договоримся, что a ≤ b.
Тогда a² ≤ ab ≤ s, то есть a ≤ √s. При s ≤ 10^12 короткая сторона принимает не более миллиона значений. Перебирать обе стороны до 10^12 не нужно.
Проверьте рассуждение
Для s = 30, p = 17 и фиксированной a = 3 какие b допустимы при a ≤ b?
Считаем все длинные стороны сразу
Из ab ≤ s получаем b ≤ s // a. Из 2(a + b) ≤ p получаем b ≤ p // 2 − a. Значит, верхняя граница B = min(s // a, p // 2 − a).
Для фиксированного a подходят целые b от a до B включительно: B − a + 1 размеров, если B ≥ a. Перебираем a, пока a² ≤ s и 2a ≤ p // 2. При этих условиях обе верхние границы не меньше a. Сумма вкладов даёт ответ; разные a отвечают разным коротким сторонам.
Сложность и ошибки
Время — O(min(√s, p)), дополнительная память — O(1). При максимальных ограничениях будет не более миллиона итераций. Ответ храните в long long; в Python используйте int.
Нечётное p округляется вниз при делении на 2: половина метра не добавляет целой стороне нового значения. Не забудьте +1 в числе целых от a до B. Квадраты учитываются один раз, поэтому делить итог на 2 нельзя.
Реализация на Python
s = int(input())
p = int(input())
half = p // 2
a = 1
answer = 0
while a * a <= s and 2 * a <= half:
last = min(s // a, half - a)
answer += last - a + 1
a += 1
print(answer)
Реализация на C++17
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
long long s,p; cin >> s >> p;
long long answer=0, half=p/2;
for (long long a=1; a*a<=s && 2*a<=half; ++a) {
long long last=min(s/a, half-a);
answer += last-a+1;
}
cout << answer << "\n";
}