题解：P1945 无边的网格

EXR_FAL · 2025-07-12 16:46:39 · 题解

题解区都没有不存在格点正三角形的证明，这里给一下

假设：

存在一个格点正三角形 \triangle ABC ，其边长为 a \in \mathbb{R}^+ 。

正三角形的面积为：

对于格点多边形，Pick 定理给出：

其中：

• 边长 $ a $ 是格点间距离，即： $$ a^2 = (\Delta x)^2 + (\Delta y)^2 \quad \text{(} \Delta x, \Delta y \in \mathbb{Z} \text{)} $$ 故 $ a^2 \in \mathbb{N} $。 由 Pick 定理，面积必须为有理数，但： $$ \frac{\sqrt{3}}{4} a^2 $$ 中 $ \sqrt{3} $ 为无理数，$ a^2 \in \mathbb{N} $，因此仅当 $ a = 0 $ 时成立，与 $ a \in \mathbb{R}^+ $ 矛盾。

结论：在标准整数格点平面中，不存在非退化的格点正三角形。）

格点正方形的思路题解区已经有了就不放了

形式化的放下代码，使用了 Java 的 Bigint 类偷懒：

import java.io.*;
import java.math.BigInteger;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(" ");
        BigInteger n = new BigInteger(input[0]);
        BigInteger m = new BigInteger(input[1]);

        if (n.compareTo(m) > 0) {
            BigInteger temp = n;
            n = m;
            m = temp;
        }

        BigInteger c1 = n.add(BigInteger.ONE);
        BigInteger c2 = n.add(BigInteger.TWO);
        BigInteger numerator = n.multiply(c1).multiply(c2).multiply(m.multiply(BigInteger.TWO).add(BigInteger.ONE).subtract(n));
        BigInteger ans = numerator.divide(BigInteger.valueOf(12));

        bw.write(ans + " 0");
        bw.close();
    }
}