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] 该函数经验证还是存在问题啊。。。。。