P1945 无边的网格 题解

P1945 无边的网格

Link: https://www.luogu.com.cn/problem/P1945

题目描述

在一个R RR行C CC列的表格中，每个单元格都是正方形。这种表格便被称为“网格”，每个单元格的四个顶点都叫做“格点”。四个顶点都在格点上的正方形叫做“格点正方形”；类似地，三个顶点都在格点上的正三角形叫做“格点正三角形”。

对于给定的正整数R RR和C CC（R , C ≤ 10 R,C \le 10R,C≤10），请计算出网格中格点正方形和格点正三角形的个数。

这种题目 GZH 已经在数学试卷上见得多了。经过浮想联翩、鸟语花香的过程，他认为它与网格问题、计数问题、对称性问题等经典数学题型有异曲同工之妙，可以很方便快捷地解出。但是同时他也发现，一旦R RR和C CC不再满足题中的条件，而是变得很大，计数将会变得枯燥。

当然，聪明的你们对此肯定是喜闻乐见，因为编程在这里又可以派上用处了。

你们能写一个程序来帮 GZH 在这无边的网格中完成枯燥的计数吗？

输入格式

共一行，包含2 22个用单个空格隔开的正整数R RR和C CC。

输出格式

共一行，包含2 22个用单个空格隔开的整数a n s 1 \mathit{ans}_1ans1​和a n s 2 \mathit{ans}_2ans2​，按序表示网格中格点正方形和格点正三角形的个数。

输入输出样例 #1

输入 #1

2 3

输出 #1

10 0

说明/提示

样例解释

输入文件表明，要求求出图中的格点正方形个数和格点正三角形个数。

• 格点正方形的个数被分类计数如下：
  
  共十个。
• 不难发现，所给的网格中找不到格点正三角形。

数据范围及约定

• 对于30 % 30\%30%的数据，R , C ≤ 50 R,C \le 50R,C≤50；
• 对于50 % 50\%50%的数据，R , C ≤ 10 3 R,C \le 10^3R,C≤103；
• 对于70 % 70\%70%的数据，R , C ≤ 10 5 R,C \le 10^5R,C≤105，A n s 1 , A n s 2 < 2 63 \mathit{Ans}_1,\mathit{Ans}_2<2^{63}Ans1​,Ans2​<263；
• 对于90 % 90\%90%的数据，R , C ≤ 10 100 R,C \le 10^{100}R,C≤10100；
• 对于100 % 100\%100%的数据，R , C ≤ 10 1000 R,C \le 10^{1000}R,C≤101000。

Solution

1. 题意

一个R × C R\times CR×C的网格，求其中能画出多少个顶点在格点上的正方形或者等边三角形。

2. 分析

边长为a aa的等边三角形面积为3 4 a 2 \dfrac{\sqrt{3}}{4}a^243​​a2。

对于一个格点三角形而言，根据皮克定理，其面积一定是整数或者带着.5 .5.5的小数，一定是有理数。

而在网格中，两点连线的长度的平方等于横坐标之差的平方加上纵坐标之差的平方，一定是有理数，因此等边三角形面积必然是无理数。如此一来可以直接宣告第二问答案为零了。

下面求解第一问。

不难看出网格会出现斜着的正方形。我们不妨设斜正方形一条边的水平方向长度为a aa，垂直方向长度为b bb，边长为a 2 + b 2 \sqrt{a^2+b^2}a2+b2​，则可以作一个四条边与坐标轴平行的，斜正方形的外接正方形，其边长为t = ∣ a ∣ + ∣ b ∣ t=|a|+|b|t=∣a∣+∣b∣。

在一个格点数量为( C + 1 ) × ( R + 1 ) (C+1)\times(R+1)(C+1)×(R+1)的矩形里（注意R , C R,CR,C是边长，格点数比边长多1 11）要放置一个t × t t\times tt×t的矩形作为正方形的外界矩形，有多少种放法？

答案是( C + 1 − t ) ( R + 1 − t ) (C+1-t)(R+1-t)(C+1−t)(R+1−t)。

而边长本身既然t = ∣ a ∣ + ∣ b ∣ t=|a|+|b|t=∣a∣+∣b∣，则斜边的“水平长度”a aa可以取值为0 , 1 , 2 , ⋯ , t − 1 0,1,2,\cdots, t-10,1,2,⋯,t−1（注意之所以没有t tt是因为，a = 0 a=0a=0和a = t a=ta=t时的正方形是重合的），有t tt种可能。

特别注意这个t tt的最大可能值是min ⁡ ( R , C ) \min(R,C)min(R,C)。如此一来，正方形的种类数就是

A n s 1 = ∑ k = 1 min ⁡ ( R , C ) t ⋅ ( R + 1 − t ) ⋅ ( C + 1 − t ) Ans_1 = \sum_{k=1}^{\min(R,C)} t \cdot (R+1-t)\cdot (C+1-t)Ans1​=k=1∑min(R,C)​t⋅(R+1−t)⋅(C+1−t)

然后代入经典的平方求和、立方求和公式

∑ k = 1 n k = n ( n + 1 ) 2 \sum_{k=1}^n k = \dfrac{n(n+1)}{2}k=1∑n​k=2n(n+1)​

∑ k = 1 n k 2 = n ( n + 1 ) ( 2 n + 1 ) 6 \sum_{k=1}^n k^2 = \dfrac{n(n+1)(2n+1)}{6}k=1∑n​k2=6n(n+1)(2n+1)​

∑ k = 1 n k 3 = n 2 ( n + 1 ) 2 4 \sum_{k=1}^n k^3 = \dfrac{n^2(n+1)^2}{4}k=1∑n​k3=4n2(n+1)2​

就能得到

A n s 1 = { C ( C + 1 ) ( C + 2 ) ( 2 R − C + 1 ) / 12 , R > C R ( R + 1 ) ( R + 2 ) ( 2 C − R + 1 ) / 12 , R ≤ C Ans_1 = \begin{cases} C(C+1)(C+2)(2R-C+1) / 12 &, R > C \\ R(R+1)(R+2)(2C-R+1) / 12 &, R \le C \end{cases}Ans1​={C(C+1)(C+2)(2R−C+1)/12R(R+1)(R+2)(2C−R+1)/12​,R>C,R≤C​

至于说高精度？

管他呢直接 Python 抬走就是了。

3. 代码

r,c=map(int,input().split())r,c=max(r,c),min(r,c)print(c*(c+1)*(c+2)*(2*r-c+1)//12,0)