N×N的方格，里面有多少个长方形？

无心人

考虑矩形右上角坐标$(x, y)$,  $(x_0, y_0)$ 为矩形内部一点，作为非平行于坐标轴的矩形的左下顶点

$x_1 = x_0 - n_1k_2$   $y_1 = y_0 + n_1k_1$ 为左上点  
$x_2 = x_0 + n_2k_1$   $y_2 = y_0 + n_2k_2$  为右下点
$x_3 =x_2-n_1k_2 =x_0+n_2k_1-n_1k_2$ $y_3 =y_2+n_1k_1=y_0+n_2k_2+n_1k_1$ 为右上点

然后，所有点都在矩形区域内的情况就是符合条件的点
即
$0 <= x_0, x_1, x_2, x_3 <= x$
$0 <= y_0, y_1, y_2, y_3 <= y$

无心人

现在我们考虑一种简化的计数形式

考虑对一组$n_1, n_2,k_1, k_2$组成的矩形$Q$
$Q$是被围在一个边平行于原始矩形的矩形$Q_s$里的

显然$Q_s$的坐标由下列值确定
$x_l = min(x_0, x_1)$  $y_b = min(y_0, y_2)$
$x_r = max(x_2, x_3)$  $y_t = max(y_1, y_3)$

由此，只需要确定$Q_s$在原矩形中能容纳多少个，
即可确定具体的$n_1, n_2,k_1, k_2$组成的矩形$Q$在原矩形中的数量

无心人

很容易知道，只要计算类型一即可

简单计算可以得到，$Q_s$的边长分别为
$n_1k_2+n_2k_1$, $n_2k_2+n_1k_1$
假设原始矩形边长分别为$m$,$n$
$1<=k_1, k_2<=min(m,n)-1$
$1<=k_1 + k_2 <= max(m + n)$

无心人

以下函数将计算非平行于四边的矩形

let countk (x, y) = if (x<=1 || y<= 1) then 0 else (sum [s |let mxy = (min x y), k1<-[1..(mxy-1)], k2<-[1..(mxy-1)], k1+k2<=(max x y), gcd k1 k2 == 1,let km = min k1 k2, n1<-[1..(div x km)], n2<-[1..(div y km)], (n1*k2+n2*k1)<=x, (n1*k1+n2*k2)<=y, let xl=x-(n1*k2+n2*k1)+1, let yl=y-(n1*k1+n2*k2)+1, let s=xl*yl])

前30的结果
map (\x-> (x, countk (x, x))) [0..30]
[(0,0),(1,0),(2,1),(3,8),(4,30),(5,88),(6,199),(7,408),(8,748),(9,1280),(10,2053),(11,3168),(12,4666),(13,6712),(14,9363),(15,12728),(16,16952),(17,22256),(18,28681),(19,36536),(20,45870),(21,56936),(22,69967),(23,85264),(24,102860),(25,123232),(26,146557),(27,173128),(28,203138),(29,237192),(30,275243)]

无心人

countk (128, 128)
150128992

即边长128的正方形里共有
150128992 + (128*129/2)^2 = 218290528
个由格点组成的矩形

无心人

现在考虑三维立方体情况

显然，边长分别为$x$, $y$, $z$的立方体
内部格点做顶点的平行于立方体六个面的立方体的个数是
${xyz(x+1)(y+1)(z+1)}/8$

无心人

然后是有一个面平行的情况

假设平行于$x, y$轴组成的平面
则结果是（以上面平面时的函数count2计算）
countk (x, y) * (div (z*(z+1) 2)^2
同理可以对其他2个面做此计算，即一共有
countk (x, y) * (div (z*(z+1) 2)^2 + countk (x, z) * (div (y*(y+1) 2)^2 + countk (z, y) * (div (x*(x+1) 2)^2
个

无心人

然后最后一种情况是所有平面都不平行情况，这个就复杂了。。。
计算了一个下午也得不到类似平面时候的三线垂直的方程来。。。。
求大牛给出坐标方程来。。。

无心人

以2X2X2为例
所有面平行是 (2*3/2)^3 = 27个
有一个平行，是  3*1*(2*3/2) = 9个
都不平行，有0个
一共36个

未确认结果，待修改

无心人

决定暴力搜索，用了个外部库求所有因子
原理是，
$(a, b, -c)$, $(x, y, z)$如果垂直，则
$ax + by + cz = 0$
然后枚举所有$a$, $b$, $x$, $y$的组合
求$t = ax + by$的一个因子c
则$z=t/c$
加上第三组，得到全部的三组向量
$(a,b,c)$,$(x,y,z)$,$(bz-cy,cx-az,ay-bx)$


Prelude Math.NumberTheory.Primes Data.List Data.Set> let d3 n = [(a,b,c,x,y,z)|a<-[1..n-1],b<-[1..n-1],gcd a b == 1, x<-[1..n-1],y<-[1..n-1], gcd x y == 1, let t=a*x+b*y, c<-(toList tl), c < n, let z=div t c, z< n]

该函数经验证还是存在问题啊。。。。。