P1945 无边的网格Link: https://www.luogu.com.cn/problem/P1945题目描述在一个R RR行C CC列的表格中每个单元格都是正方形。这种表格便被称为“网格”每个单元格的四个顶点都叫做“格点”。四个顶点都在格点上的正方形叫做“格点正方形”类似地三个顶点都在格点上的正三角形叫做“格点正三角形”。对于给定的正整数R RR和C CCR , 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输入 #12 3输出 #110 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≤105A n s 1 , A n s 2 2 63 \mathit{Ans}_1,\mathit{Ans}_22^{63}Ans1,Ans2263对于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。Solution1. 题意一个R × C R\times CR×C的网格求其中能画出多少个顶点在格点上的正方形或者等边三角形。2. 分析边长为a aa的等边三角形面积为3 4 a 2 \dfrac{\sqrt{3}}{4}a^243a2。对于一个格点三角形而言根据皮克定理其面积一定是整数或者带着.5 .5.5的小数一定是有理数。而在网格中两点连线的长度的平方等于横坐标之差的平方加上纵坐标之差的平方一定是有理数因此等边三角形面积必然是无理数。如此一来可以直接宣告第二问答案为零了。下面求解第一问。不难看出网格会出现斜着的正方形。我们不妨设斜正方形一条边的水平方向长度为a aa垂直方向长度为b bb边长为a 2 b 2 \sqrt{a^2b^2}a2b2则可以作一个四条边与坐标轴平行的斜正方形的外接正方形其边长为t ∣ a ∣ ∣ b ∣ t|a||b|t∣a∣∣b∣。在一个格点数量为( C 1 ) × ( R 1 ) (C1)\times(R1)(C1)×(R1)的矩形里注意R , C R,CR,C是边长格点数比边长多1 11要放置一个t × t t\times tt×t的矩形作为正方形的外界矩形有多少种放法答案是( C 1 − t ) ( R 1 − t ) (C1-t)(R1-t)(C1−t)(R1−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 a0a0和a t atat时的正方形是重合的有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_{k1}^{\min(R,C)} t \cdot (R1-t)\cdot (C1-t)Ans1k1∑min(R,C)t⋅(R1−t)⋅(C1−t)然后代入经典的平方求和、立方求和公式∑ k 1 n k n ( n 1 ) 2 \sum_{k1}^n k \dfrac{n(n1)}{2}k1∑nk2n(n1)∑ k 1 n k 2 n ( n 1 ) ( 2 n 1 ) 6 \sum_{k1}^n k^2 \dfrac{n(n1)(2n1)}{6}k1∑nk26n(n1)(2n1)∑ k 1 n k 3 n 2 ( n 1 ) 2 4 \sum_{k1}^n k^3 \dfrac{n^2(n1)^2}{4}k1∑nk34n2(n1)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(C1)(C2)(2R-C1) / 12 , R C \\ R(R1)(R2)(2C-R1) / 12 , R \le C \end{cases}Ans1{C(C1)(C2)(2R−C1)/12R(R1)(R2)(2C−R1)/12,RC,R≤C至于说高精度管他呢直接 Python 抬走就是了。3. 代码r,cmap(int,input().split())r,cmax(r,c),min(r,c)print(c*(c1)*(c2)*(2*r-c1)//12,0)
