形式化题目

给定三个顶点 $O(0,0)$、$A(n,m)$、$C(p,0)$（$0\leqslant n<32000$，$0<m<32000$，$0<p<32000$）， 它们都是整点。求严格落在三角形 $OAC$ 内部（不含三条边）的整点个数。

输入一行三个整数 $n\ m\ p$，输出一个整数表示内部整点数。

正解

思路

朴素做法与它的瓶颈

最直接的做法是圈出三角形的包围盒 $0\leqslant x\leqslant \max(n,p)$、$0\leqslant y\leqslant m$， 逐个枚举格点，再用叉积判断它是否在三角形内部。

包围盒规模最坏是 $3\times10^4 \times 3\times10^4 = 9\times10^8$ 个格点。 这不只是「Python 慢」的常数问题——逐点枚举这个建模方式本身就是 $O(nm)$ 的， 换 C++ 也不划算。要真正提速，必须把「数格点」换成「算几何量」。

关键观察：顶点全为格点时，Pick 定理把计数变成代数

Pick 定理说：对顶点全为格点的简单多边形，

其中 $S$ 是面积，$I$ 是多边形内部的整点数，$B$ 是多边形边界上的整点数。 而我们要求的正好就是 $I$，所以只要算出 $S$ 与 $B$：

面积是 $O(1)$。 三个顶点里有一个是原点，鞋带公式只剩一项：

因为 $m>0,\ p>0$，绝对值可以直接去掉。

边界整点数只需三次 gcd。 端点为整点的线段 $(x_1,y_1)\to(x_2,y_2)$ 上， 整点个数为 $\gcd(|\Delta x|,|\Delta y|)+1$。三条边分别是：

三边相加时，三个顶点各被相邻两条边数了一次，共重复 3 次，减掉：

以测试数据 fence91（$n=2,m=2,p=4$）为例：$\gcd(2,2)=2$，$\gcd(|4-2|,2)=2$，$p=4$， 故 $B = 2+2+4 = 8$，与上表「$3+3+5-3=8$」一致。

合成最终公式

把 $2S$ 与 $B$ 代回，两边乘 2 以避开小数：

Pick 定理保证分子必为偶数，所以直接用整数除法 // 就是精确答案。

下面画出 $n=2,m=2,p=4$ 的格点图，○ 是边上的整点、● 是内部整点、· 是外部： 可以看到边界恰好 8 个点，内部只有 $(2,1)$ 一个。

1
2
3
4y=2  · · ○ · ·
y=1  · ○ ● ○ ·
y=0  ○ ○ ○ ○ ○
     x0 x1 x2 x3 x4

代入公式验证：$2S=8$，$B=8$，$I=(8-8+2)/2=1$，与图中唯一的 ● 吻合。 这张图把 $S$、$B$、$I$ 三量的关系完整展示了一遍：面积减去边界贡献再补回常数 1， 剩下的恰好是内部整点数。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 06:07
# update_at: 2026-10-01 06:07

import sys
from math import gcd


def interior_points(n: int, m: int, p: int) -> int:
    """返回三角形 (0,0),(n,m),(p,0) 内部（不含边界）的整点数。

    Pick 定理 I = S - B/2 + 1；这里改用两倍量避免小数：
    I = (2S - B + 2) / 2，其中 2S = p*m，B 是三条边上的整点数之和。
    """
    area2 = p * m                                          # 鞋带公式的两倍面积
    boundary = gcd(n, m) + gcd(abs(p - n), m) + p           # 三条边的 gcd 之和
    return (area2 - boundary + 2) // 2


def solve() -> None:
    n, m, p = map(int, sys.stdin.buffer.read().split())
    print(interior_points(n, m, p))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 10:30
 * update_at: 2026-10-06 10:30
 */

// usaco-3.4.3 fence9：数三角形 (0,0),(n,m),(p,0) 内部的整点数。
// Pick 定理 S = I + B/2 - 1，移项并用两倍量避免小数：
//   2S = p * m
//   B  = gcd(n,m) + gcd(|p-n|,m) + p   （三条边上的整点数，顶点重复计数已扣掉）
//   I  = (2S - B + 2) / 2
#include <cstdio>
using namespace std;

typedef long long ll;

ll n, m, p; // 三角形三个顶点 (0,0)、(n,m)、(p,0)

// 欧几里得算法求最大公约数，供统计边界整点数使用
ll gcd_ll(ll a, ll b) {
    while (b != 0) {
        ll t = a % b;
        a = b;
        b = t;
    }
    return a;
}

int main() {
    scanf("%lld %lld %lld", &n, &m, &p);

    ll area2 = p * m;                                      // 鞋带公式给出的两倍面积
    ll boundary = gcd_ll(n, m) + gcd_ll(p - n < 0 ? n - p : p - n, m) + p; // 三边整点数
    ll interior = (area2 - boundary + 2) / 2;              // Pick 定理求内部整点数

    printf("%lld\n", interior);
    return 0;
}

复杂度

• 时间：$O(\log\min(n,m))$，即三次 gcd；在本题上限下几乎是常数，实测单组约 0.018s。
• 空间：$O(1)$。

用真实数据验证：12 组数据（含 $n=0$ 的退化三角形、$n,p$ 取到 30000 的大数据） 输出全部与标准答案一致，单组峰值内存约 14.7 MB。

总结

顶点全为格点的多边形，「内部整点数」不需要逐点枚举：Pick 定理 $S=I+\frac{B}{2}-1$ 把它化归为「面积 + 边界整点数」。本题三角形一个顶点在原点、一个在 $x$ 轴上， 使 $2S=pm$、$B=\gcd(n,m)+\gcd(|p-n|,m)+p$ 都退化成一行式子， 于是 $O(nm)$ 的枚举被压成 $O(\log)$ 的常数次 gcd。