Я хочу рассчитать количество прямоугольников в прямоугольниках. Это можно сделать с помощью формулы
(x^2+x)(y^2+y)/4
но он также включает в себя идеальные квадраты, такие как 1 * 1,2 * 2,3 * 3 и т. д. Я не хочу включать это в свои расчеты. Как я могу это сделать?
Хорошо, у вас есть количество прямоугольников с целочисленными координатами между точками (0, 0), (x, 0), (x, y) и (0, y), x и y тоже целыми числами. Теперь вам нужно удалить идеальные квадраты из этой суммы.
Чтобы его вычислить, оценим количество квадратов 1*1: их, очевидно, x*y. Для квадратов 2*2 у нас есть x-1 вариантов для координаты x и y-1 для координаты y нижнего левого угла такого квадрата из-за ширины этого квадрата: в результате получается (x-1)*(y-1) квадратов. То же самое, у нас будет (x-2)*(y-2) квадратов 3*3 и т.д.
Итак, для данного i у нас есть (x - i + 1) * (y - i + 1) квадратов i*i, а i идет от 1 до минимума x и y (конечно, если x равно 4, а y равно 7, у нас не может быть квадрата со стороной больше 4).
Итак, если m = min(x, y), у нас есть:
Sum_Squares = Sum(i = 1, i = m, (x - i + 1) * (y - i + 1))
= Sum(j = 0, j = m - 1, (x - i) * (y - i))
= Sum(j = 0, j = m - 1, x*y - (x+y)*j + j^2)
= m*x*y - (x+y)*Sum(j = 0, j = m - 1, j) + Sum(j = 0, j = m - 1, j^2)
= m*x*y - (x+y)*Sum(j = 1, j = m - 1, j) + Sum(j = 1, j = m - 1, j^2)
= m*x*y - (x+y)*m*(m-1)/2 + (m-1)*m*(2*m-1)/6
Я получаю это с изменением индекса (j = i - 1) и с помощью известных формул:
Sum(i = 1, i = n, j) = n*(n + 1)/2
Sum(i = 1, i = n, j^2) = n*(n + 1)*(2*n + 1)/6
Вам просто нужно удалить этот Sum_Squares из (x^2+x)(y^2+y)/4 и все готово!
