一点一点前进...

0%

欧拉项目 | 504题 | 多少个四边形包含平方个数目的点？

发表于 分类于 ， Disqus：

原题链接

四边形ABCD，各点位于四个坐标轴上，坐标分别是A(a, 0), B(0, b), C(−c, 0), D(0, −d)，其中1 ≤ a, b, c, d ≤ m 并且a, b, c, d, m都是整数。

比如m = 4, 四边形ABCD共有256种情况。256个四边形当中，有42四边形精确地包含平方个数目的网格点（坐标为整数）。

如果m = 100, 有多少个四边形包含平方个数目的点呢？

对于现代计算机而言，遍历100 ^ 4其实是很快的一件事情，如果对于每一个四边形而言，如果能在常数量级得到包含点的个数，然后常数量级知道它是不是平方数，那么就基本能在100 ^ 4这个量级搞定这个问题。

常数量级知道某个数是不是平方数很简单，先算出来一个列表，然后去查询就可以了。
ABCD能组成最大的正方形就是边长约为141的正方形，内部点最多也就是140 * 140个，那么，把前140个平方数存下来，之后用二分法查找即可。

1
var squares = Enumerable.Range(1, 140).Select(n => n * n).ToList();

那么如何知道四边形里面点的个数呢？
预先存下来。
显然不是预先存下来每个四边形的点的个数，这不就是我们要的结果嘛。
我们存储直角三角形的内部点的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static private int[,] NumbersOfInsideVector = new int[M + 1, M + 1];

for (int i = 1; i <= M; i++)
{
	for (int j = 1; j <= i; j++)
	{
		int result = GetInsideVector(i, j);
		NumbersOfInsideVector[i, j] = result;
		NumbersOfInsideVector[j, i] = result;
	}
}

private static int GetInsideVector(int a, int b)
{
	int count = 0;

	for (int i = 1; i <= a - 1; i++)
	{
		int yi = b - b * i / a;
		count += (yi - 1);
	}

	return count;
}

使用一个二维数组来存放边长为a b的直角三角形内部的点数。对于边长a b的直角三角形，x轴从1到a - 1，计算高度yi，然后得到对于每个x有的点数，相加起来就是整个直角三角形内部的点数了。
整个计算过程，外层是O(M ^ 2)，GetInsideVector是O(M)，总的复杂度上限是O(M ^ 3)。

有了直角三角形内部点数，计算ABCD四边形内部点数就非常容易了。

1
2
3
4
5
6
7
8
9
10
private static int GetNumberOfVector(int a, int b, int c, int d)
{
	int number = a + b + c + d + -3;
	number += NumbersOfInsideVector[a, b];
	number += NumbersOfInsideVector[b, c];
	number += NumbersOfInsideVector[c, d];
	number += NumbersOfInsideVector[d, a];

	return number;
}

除了计算几个直角三角形内部的点数，还要加上坐标轴上的点，a b c d相加再减去3个，这是重复计算了原点。
我们有能力在O(1)时间内搞定任意一个四边形内部点的个数，最后就是遍历每一个可能的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
long count = 0;

for (int d = 1; d <= M; d++)
{
	for (int c = 1; c <= M; c++)
	{
		for (int b = 1; b <= M; b++)
		{
			for (int a = 1; a <= M; a++)
			{
				int numberOfVector = GetNumberOfVector(a, b, c, d);
				if (squares.BinarySearch(numberOfVector) >= 0)
				{
					count++;
				}
			}
		}
	}
}

return count;

在我的机器上，i5-5257U的电脑，大约8s能够解决这个问题，还算是挺快。