墙壁划线

[题目链接](https://www.nowcoder.com/practice/fbae28533ca04bd0ba088329cb46210d)

思路

题目给了一面由 $n \times m$ 块瓷砖组成的墙壁，每块瓷砖是 $a \times b$ 的矩形，所以整面墙的尺寸是 $na \times mb$ 。要从左上角到右下角、从右上角到左下角各画一条对角线，问这两条线一共与瓷砖的边界线产生多少个交点。

一条对角线穿过多少个交点？

先看一条对角线，比如从 $(0, 0)$ 到 $(na, mb)$ 。瓷砖的边界线就是网格线：竖直方向在 $x = a, 2a, \ldots, (n-1)a$ ，水平方向在 $y = b, 2b, \ldots, (m-1)b$ 。

对角线穿过的内部竖直网格线有 $n - 1$ 条，穿过的内部水平网格线有 $m - 1$ 条。但如果对角线恰好经过某个网格交叉点（竖直线和水平线的交点），那在那个位置只算一个交点，不能重复计数。

对角线经过内部网格交叉点 $(ia, jb)$ 的条件是 $\frac{i}{n} = \frac{j}{m}$ ，即 $im = jn$ 。满足 $1 \leq i \leq n-1$ 的解的个数恰好是 $\gcd(n, m) - 1$ 。

所以一条对角线在内部产生的交点数是：

(n - 1) + (m - 1) - (\gcd(n, m) - 1) = n + m - \gcd(n, m) - 1

再加上两个端点（墙壁的角落也是网格线的交点），一条对角线的总交点数为：

f(n, m) = n + m - \gcd(n, m) + 1

两条对角线合在一起

两条对角线各自的交点数都是 $f(n, m)$ ，但它们可能有重合的交点。两条对角线唯一的公共点是墙壁的中心 $(\frac{na}{2}, \frac{mb}{2})$ 。这个中心点在网格线上（从而被两条对角线各计数一次）当且仅当 $n$ 是偶数（中心在竖直网格线上）或 $m$ 是偶数（中心在水平网格线上）。

因此最终答案为：

\text{ans} = 2 \cdot f(n, m) - [n \text{ 为偶数或 } m \text{ 为偶数}]

其中方括号表示布尔值（成立则为 1，否则为 0）。注意 $a$ 和 $b$ 在公式中完全不出现——它们只决定每块瓷砖的形状，不影响网格线的拓扑结构。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;
int main(){
    long long n, m, a, b;
    cin >> n >> m >> a >> b;
    long long g = __gcd(n, m);
    long long one = n + m - g + 1;
    long long ans = 2 * one;
    if(n % 2 == 0 || m % 2 == 0) ans--;
    cout << ans << endl;
    return 0;
}

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong(), m = sc.nextLong(), a = sc.nextLong(), b = sc.nextLong();
        long g = gcd(n, m);
        long one = n + m - g + 1;
        long ans = 2 * one;
        if (n % 2 == 0 || m % 2 == 0) ans--;
        System.out.println(ans);
    }
    static long gcd(long a, long b) {
        while (b != 0) { long t = b; b = a % b; a = t; }
        return a;
    }
}

from math import gcd
n, m, a, b = map(int, input().split())
g = gcd(n, m)
one = n + m - g + 1
ans = 2 * one
if n % 2 == 0 or m % 2 == 0:
    ans -= 1
print(ans)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
rl.on('line', (line) => {
    const [n, m, a, b] = line.trim().split(' ').map(Number);
    function gcd(a, b) { while (b) { [a, b] = [b, a % b]; } return a; }
    const g = gcd(n, m);
    const one = n + m - g + 1;
    let ans = 2 * one;
    if (n % 2 === 0 || m % 2 === 0) ans--;
    console.log(ans);
    rl.close();
});

复杂度分析

时间复杂度： $O(\log(\min(n, m)))$ ，瓶颈在求 $\gcd$ 。
空间复杂度： $O(1)$ 。