如何計算矩形網格中的矩形數量？

Question

我要計算在rectangles.It矩形的數目可以使用式

（X^2 + X）（Y^2 + Y）/ 4

但它也包括完全平方等來進行1 * 1,2 * 2,3 * 3等。我不想在我的計算中包括那個。我該怎麼做？

Answer 1

好吧，你有整數矩形數點(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，你就完成了！