题解 | #墙壁划线#

题目链接

题目描述

一面尺寸为 $(a \cdot x) \times (b \cdot y)$ 的矩形墙壁由 $a \cdot b$ 块尺寸为 $x \times y$ 的瓷砖铺成。现从墙的左上角到右下角、右上角到左下角各画一条直线。求这两条直线与所有瓷砖边界线形成的交点总数。

解题思路

这是一个几何计数问题，可以通过坐标法和数论知识解决。

简化问题

首先，一个关键的观察是，交点的数量只与瓷砖的行列数 $a$ 和 $b$ 有关，而与每块瓷砖的具体尺寸 $x$ 和 $y$ 无关。我们可以将问题简化为在一个 $a \times b$ 的单位格网格上进行分析。

计算单条对角线的交点数

我们先考虑从左上角 (0, 0) 到右下角 (a, b) 的这条对角线。

它穿过的垂直网格线共有 $a+1$ 条（从 $u=0$ 到 $u=a$ ）。
它穿过的水平网格线共有 $b+1$ 条（从 $v=0$ 到 $v=b$ ）。

如果我们直接将这两个数量相加，即 (a+1) + (b+1)，那些恰好穿过网格顶点（即横纵坐标均为整数的点）的交点会被计算两次。因此，我们需要减去重复计算的顶点数。

根据数论中的一个经典结论，一条从 (0, 0) 连接到 (a, b) 的直线所经过的整数坐标点的数量为 $\gcd(a, b) + 1$ 。

利用容斥原理，单条对角线与网格线的交点总数为：

$(a+1) + (b+1) - (\gcd(a, b) + 1) = a + b - \gcd(a, b) + 1$

计算两条对角线的总交点数

由于对称性，两条对角线各自与网格线的交点数量是相同的。因此，我们先将单条对角线的交点数乘以2，得到一个初步的总数：

$2 \cdot (a + b - \gcd(a, b) + 1)$

这个计算假设了两条对角线上的交点集合是不相交的。但实际上，它们可能存在公共交点。两条对角线唯一的物理交点是整个矩形的中心，即 (a/2, b/2)。

我们需要判断这个中心点是否是一个被我们重复统计的“网格线交点”。

如果 $a$ 是偶数，中心点的横坐标 $a/2$ 就是一个整数，该点落在一条垂直网格线上。
如果 $b$ 是偶数，中心点的纵坐标 $b/2$ 就是一个整数，该点落在一条水平网格线上。

只要满足 $a$ 为偶数或 $b$ 为偶数两者之一，中心点就是一个有效的“网格线交点”。这个点在计算两条对角线时都被统计了一次，因此被重复计算了。我们需要从总数中减去 1。

最终公式

综上所述，最终的交点总数 $ans$ 为：

$ans = 2 \cdot (a + b - \gcd(a, b) + 1)$
如果 $a$ 是偶数或 $b$ 是偶数，则 $ans = ans - 1$

代码

c++
java
python

#include <iostream>
#include <numeric>

using namespace std;

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

int main() {
    long long a, b, x, y;
    cin >> a >> b >> x >> y;
    
    long long ans = 2 * (a + b - gcd(a, b) + 1);
    
    if (a % 2 == 0 || b % 2 == 0) {
        ans--;
    }
    
    cout << ans << endl;
    
    return 0;
}

import java.util.Scanner;

public class Main {
    public 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 ans = 2 * (a + b - gcd(a, b) + 1);
        
        if (a % 2 == 0 || b % 2 == 0) {
            ans--;
        }
        
        System.out.println(ans);
    }
}

import math

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

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

ans = 2 * (a + b - gcd(a, b) + 1)

if a % 2 == 0 or b % 2 == 0:
    ans -= 1

print(ans)

算法及复杂度

算法：数学、数论、最大公约数( $\gcd$ )
时间复杂度：主要计算开销来自于最大公约数函数，其时间复杂度为 $\mathcal{O}(\log(\min(a, b)))$ 。
空间复杂度：只使用了常数个变量，空间复杂度为 $\mathcal{O}(1)$ 。