Хорошо, у вас есть число прямоугольников с целочисленными координатами между точками (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 и все готово!