Блог

Я хочу вычислить количество прямоугольников в rectangles.Это можно сделать с помощью формулы

(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 , и все готово !