题解 | #墙壁划线#

题目链接

墙壁划线

题目描述

一块矩形墙壁由 $n \times m$ 块尺寸为 $a \times b$ 的瓷砖构成。

现在要从墙壁的左上角向右下角、右上角向左下角划两条对角线。

请问，这两条对角线与所有瓷砖的边界线（包括墙壁外边界）总共产生了多少个交点？

解题思路

这是一个有趣的几何计数问题，其解法不依赖于瓷砖的具体尺寸 $a$ 和 $b$ ，而只与瓷砖的行列数 $n$ 和 $m$ 有关。

问题的关键是精确理解题目要求：计算对角线与瓷砖边界线相交形成的点有多少个。这意味着，两条对角线自身的交点（矩形中心），只有当它恰好落在某条边界线上时，才被计数。

我们可以将问题分解：

计算单条对角线与网格线（瓷砖边界）的交点数。
使用容斥原理合并两条对角线的结果，处理共同的交点。

1. 单条对角线的交点数

考虑从左下角到右上角的对角线。它穿过一个由 $n \times m$ 个单元格组成的网格。

这条对角线会穿过 $n-1$ 条内部的垂直线和 $m-1$ 条内部的水平线。
如果对角线不经过任何网格的顶点，它将产生 $(n-1) + (m-1)$ 个内部交点。
然而，当对角线穿过一个顶点时，一个水平交点和一个垂直交点会重合。穿过的内部顶点数等于 $\text{gcd}(n, m) - 1$ 。
所以，对角线与内部网格线的交点数是 $(n-1) + (m-1) - (\text{gcd}(n, m) - 1) = n + m - \text{gcd}(n, m) - 1$ 。
题目要求计算与所有边界线的交点，包括外边界。对角线的起点和终点是两个额外的交点。
因此，单条对角线产生的总交点数（我们称之为 single_points）为： single_points = (n + m - gcd(n, m) - 1) + 2 = n + m - gcd(n, m) + 1

2. 合并计算

设 $S_1$ 为第一条对角线与边界线的交点集合， $S_2$ 为第二条的。我们要求的是 $|S_1 \cup S_2| = |S_1| + |S_2| - |S_1 \cap S_2|$ 。

$|S_1|$ 和 $|S_2|$ 的大小都等于我们上面计算的 single_points。
$|S_1 \cap S_2|$ 是两条对角线共同的、且落在边界线上的交点数。这样的点只有一个可能——矩形的中心。
矩形中心落在边界线上，当且仅当 $n$ 或 $m$ 至少有一个为偶数。
- 如果 $n$ 或 $m$ 为偶数，中心点在边界线上，是两条对角线唯一的共同交点。所以 $|S_1 \cap S_2| = 1$ 。
- 如果 $n$ 和 $m$ 均为奇数，中心点不在任何边界线上，因此两条对角线与边界线的交点集没有重合。所以 $|S_1 \cap S_2| = 0$ 。

3. 最终公式

Case 1: $n$ 和 $m$ 均为奇数。 总交点数 = $|S_1| + |S_2| - 0 = 2 \cdot \text{single\_points}$ 。
Case 2: $n$ 或 $m$ 至少有一个为偶数。 总交点数 = $|S_1| + |S_2| - 1 = 2 \cdot \text{single\_points} - 1$ 。

代码

c++
java
python

#include <iostream>
#include <numeric> // For std::gcd in C++17
#include <utility> // For std::swap

// 自定义 gcd 函数以兼容旧版本编译器
long long gcd(long long a, long long b) {
    while (b) {
        a %= b;
        std::swap(a, b);
    }
    return a;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    long long n, m, a, b;
    std::cin >> n >> m >> a >> b;

    long long common_divisor = gcd(n, m);

    // 计算单条对角线与所有网格线的交点数
    long long single_diag_points = n + m - common_divisor + 1;

    long long total_points;
    if (n % 2 != 0 && m % 2 != 0) {
        // n 和 m 均为奇数，中心点不在网格线上，没有共同交点
        total_points = 2 * single_diag_points;
    } else {
        // n 或 m 至少有一个为偶数，中心点是唯一的共同交点
        total_points = 2 * single_diag_points - 1;
    }

    std::cout << total_points << std::endl;

    return 0;
}

import java.util.Scanner;
import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long m = sc.nextLong();
        long a = sc.nextLong();
        long b = sc.nextLong();
        
        BigInteger n_bi = BigInteger.valueOf(n);
        BigInteger m_bi = BigInteger.valueOf(m);
        
        long commonDivisor = n_bi.gcd(m_bi).longValue();
        
        // 计算单条对角线与所有网格线的交点数
        long singleDiagPoints = n + m - commonDivisor + 1;
        
        long totalPoints;
        if (n % 2 != 0 && m % 2 != 0) {
            // n 和 m 均为奇数，中心点不在网格线上，没有共同交点
            totalPoints = 2 * singleDiagPoints;
        } else {
            // n 或 m 至少有一个为偶数，中心点是唯一的共同交点
            totalPoints = 2 * singleDiagPoints - 1;
        }
        
        System.out.println(totalPoints);
    }
}

import sys
import math

def solve():
    try:
        n, m, a, b = map(int, sys.stdin.readline().split())
        
        common_divisor = math.gcd(n, m)
        
        # 计算单条对角线与所有网格线的交点数
        single_diag_points = n + m - common_divisor + 1
        
        if n % 2 != 0 and m % 2 != 0:
            # n 和 m 均为奇数，中心点不在网格线上，没有共同交点
            total_points = 2 * single_diag_points
        else:
            # n 或 m 至少有一个为偶数，中心点是唯一的共同交点
            total_points = 2 * single_diag_points - 1
            
        print(total_points)
        
    except (IOError, ValueError):
        return

solve()

算法及复杂度

算法：数学 / 几何计数 / 容斥原理
时间复杂度: $\mathcal{O}(\log(\min(n, m)))$ 。主要的时间开销来自于计算最大公约数（GCD）。
空间复杂度: $\mathcal{O}(1)$ 。