题解 | #墙壁划线#

题目链接

墙壁划线

题目描述

一面矩形墙壁由 $a \cdot b$ 块完全一致的瓷砖铺成，每块瓷砖尺寸为 $x \cdot y$ 。现在从墙的左上角到右下角、右上角到左下角各画一条直线。请求出这两条直线与所有瓷砖边界线（包括墙壁的边界）形成的交点总数。

输入:

一行输入四个正整数 $a, b, x, y$ 。

输出:

输出一个整数，表示交点总数。

解题思路

这是一个典型的几何计数问题，核心是利用容斥原理计算不同交点的数量。

首先，一个关键的观察是：瓷砖的具体尺寸 $x$ 和 $y$ 不影响交点的数量。交点的数量仅取决于墙壁由多少块瓷砖组成，即 $a$ 和 $b$ 的值。因为对角线方程与瓷砖边界方程求解交点时， $x$ 和 $y$ 因子可以被约去，交点模式只和 $a, b$ 的比例有关。因此，我们可以忽略输入中的 $x$ 和 $y$ 。

我们的目标是计算两条对角线与网格线（瓷砖边界）交点的并集大小。设 $S_1$ 为第一条对角线（左上到右下）与网格线的交点集合， $S_2$ 为第二条对角线（右上到左下）的交点集合。我们要求的就是 $|S_1 \cup S_2|$ 。根据容斥原理： $|S_1 \cup S_2| = |S_1| + |S_2| - |S_1 \cap S_2|$ 。

计算单条对角线的交点数 $|S_1|$
- 一面 $a \cdot b$ 的瓷砖墙，有 $a+1$ 条垂直网格线和 $b+1$ 条水平网格线（包括边界）。
- 一条对角线会穿过这些网格线形成交点。如果它直接穿过一个网格顶点（横线和竖线的交点），那么这个点只算一个交点。
- 一条从 $(0,0)$ 到 $(a,b)$ 的对角线穿过的网格顶点数（不含起点终点）为 $\gcd(a,b)-1$ 。算上起点和终点，共穿过 $\gcd(a,b)+1$ 个顶点。
- 使用容斥原理计算单条对角线的交点数： $|S_1| = (\text{垂直线数}) + (\text{水平线数}) - (\text{顶点数})$ $|S_1| = (a+1) + (b+1) - (\gcd(a,b)+1) = a+b+1-\gcd(a,b)$ 。
计算 $|S_2|$
- 由于对称性， $|S_2| = |S_1| = a+b+1-\gcd(a,b)$ 。
计算两条对角线共同的交点数 $|S_1 \cap S_2|$
- 两条对角线唯一的交点是矩形墙壁的中心点。
- 只有当这个中心点恰好落在某条网格线上时，它才会被我们计入 $|S_1|$ 和 $|S_2|$ 。
- 墙壁的中心点坐标可以表示为 $(a/2, b/2)$ （以瓷砖数为单位）。
- 这个点落在垂直网格线上，当且仅当 $a$ 是偶数。
- 这个点落在水平网格线上，当且仅当 $b$ 是偶数。
- 因此，只要 $a$ 或 $b$ 中至少有一个是偶数，中心点就会落在网格线上，并被重复计算。此时 $|S_1 \cap S_2| = 1$ 。
- 如果 $a$ 和 $b$ 都是奇数，中心点不在任何网格线上， $|S_1 \cap S_2| = 0$ 。
汇总
- 将上述结果代入总公式，得到最终交点数： $2 \cdot (a+b+1-\gcd(a,b)) - (\text{1 if } a \text{ or } b \text{ is even, else 0})$

代码

cpp
java
python

#include <iostream>
#include <numeric>

using namespace std;
using LL = long long;

LL gcd(LL a, LL b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    LL a, b, x, y;
    cin >> a >> b >> x >> y;
    
    LL total_points = 2 * (a + b + 1 - gcd(a, b));
    if (a % 2 == 0 || b % 2 == 0) {
        total_points--;
    }
    
    cout << total_points << endl;
    
    return 0;
}

import java.util.Scanner;

public class Main {
    static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();
        long x = sc.nextLong();
        long y = sc.nextLong();
        
        long total_points = 2 * (a + b + 1 - gcd(a, b));
        if (a % 2 == 0 || b % 2 == 0) {
            total_points--;
        }
        
        System.out.println(total_points);
    }
}

import math

def gcd(a, b):
    return math.gcd(a, b)

a, b, x, y = map(int, input().split())

total_points = 2 * (a + b + 1 - gcd(a, b))
if a % 2 == 0 or b % 2 == 0:
    total_points -= 1

print(total_points)

算法及复杂度

算法：数学、容斥原理、最大公约数(GCD)
时间复杂度： $\mathcal{O}(\log(\min(a,b)))$ ，主要开销来自计算最大公约数。
空间复杂度： $\mathcal{O}(1)$ 。