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

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

题目描述

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

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

• $B$ 与 $C$ 都是上述整点，且都不与 $A$ 重合；
• $B\ne C$；
• 由点 $A,B,C$ 构成的三角形面积为整数。

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

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

输入格式

无

输出格式

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

输入输出样例 #1

输入 #1

输出 #1

Solution

1. 题意

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

2. 分析

由原点 $A(0,0)$、$B(x_B,y_B)$、$C(x_C,y_C)$ 组成的三角形的面积为

$$S=\frac{1}{2}|x_B{y}_C-x_C{y}_B|$$

因此对于每一组点，只需要判断 $x_B{y}_C-x_C{y}_B$ 是不是偶数即可。特别的，直接四重循环那将是大约 $1.69\times 10^{13}$ 的规模，必须要利用奇偶性思路来分类讨论。

奇偶性表

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

print(5277593321988)