P16283 [蓝桥杯 2026 省 Python A 组] 平面选点

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

题目描述

在平面直角坐标系中，固定点A AA为坐标原点( 0 , 0 ) (0, 0)(0,0)。

现在，考虑所有横坐标、纵坐标都在0 00到2026 20262026之间的整点。请你统计满足下列条件的点对{ B , C } \{B, C\}{B,C}的数量：

• B BB与C CC都是上述整点，且都不与A AA重合；
• B ≠ C B \neq CB=C；
• 由点A , B , C A, B, CA,B,C构成的三角形面积为整数。

其中，若A , B , C A, B, CA,B,C三点共线，则三角形面积记为0 00，这种情况也计入答案。

点对{ B , C } \{B, C\}{B,C}不区分顺序，即{ B , C } \{B, C\}{B,C}与{ C , B } \{C, B\}{C,B}视为同一点对。

输入格式

无

输出格式

这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

输入输出样例 #1

输入 #1

输出 #1

Solution

1. 题意

A AA是原点，B , C B,CB,C是横纵坐标均为[ 0 , 2026 ] [0,2026][0,2026]范围的整数的点，求有多少三角形△ A B C △ABC△ABC（三点共线的退化三角形也算）的面积是整数。

2. 分析

由原点A ( 0 , 0 ) A(0,0)A(0,0)、B ( x B , y B ) B(x_B,y_B)B(xB​,yB​)、C ( x C , y C ) C(x_C,y_C)C(xC​,yC​)组成的三角形的面积为

S = 1 2 ∣ x B y C − x C y B ∣ S = \dfrac{1}{2}|x_By_C - x_Cy_B|S=21​∣xB​yC​−xC​yB​∣

因此对于每一组点，只需要判断x B y C − x C y B x_By_C - x_Cy_BxB​yC​−xC​yB​是不是偶数即可。特别的，直接四重循环那将是大约1.69 × 10 13 1.69\times 10^{13}1.69×1013的规模，必须要利用奇偶性思路来分类讨论。

奇偶性表

最后能得到答案是5 , 277 , 593 , 321 , 988 \boxed{5,277,593,321,988}5,277,593,321,988​。

print(5277593321988)