题目链接

墙壁划线

题目描述

某块矩形墙壁由 块瓷砖构成，每块瓷砖都是 的矩形。
现在想要从左上角向右下角，从右上角向左下角划两条直线，请问直线与每块瓷砖的边界线产生的交点共有多少个？

输入:

  • 一行四个正整数：、、、，分别表示墙壁的瓷砖数（长×宽）和单个瓷砖的尺寸（长×宽）

输出:

  • 一个正整数，表示交点的数目

解题思路

这是一个复杂的几何问题，需要考虑以下几种情况：

  1. 首先需要处理瓷砖尺寸：

    • 对瓷砖的长宽 进行约分（除以最大公约数）
    • 这样可以得到最简化的瓷砖比例

  2. 分两种主要情况讨论：

    • 情况1：当墙壁长宽相等时（）
      • 交点数 =
      • 如果 或 是偶数，需要减去1（因为对角线会重合）
    • 情况2：当墙壁长宽不等时（）
      • 基础交点数 =
      • 需要减去
      • 如果 或 是偶数，同样需要减去1

  3. 特别注意：

    • 需要使用长整型(long long)避免溢出
    • 使用 函数计算最大公约数

代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main() {
    LL a, b, x, y;
    cin >> a >> b >> x >> y;
    LL ans = 0;
    auto g = gcd(x, y);
    x /= g;
    y /= g;
    if (a == b) {
        ans = a + 1 + b + 1;
        if (a % 2 == 0 || b % 2 == 0) ans--;
    } else {
        ans = (a + 1) * 2 + (b + 1) * 2 - 2 * (gcd(a, b) + 1);
        if (a % 2 == 0 || b % 2 == 0) ans--;
    }
    cout << ans << endl;
}

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 g = gcd(x, y);
        x /= g;
        y /= g;
        
        long ans;
        if (a == b) {
            ans = a + 1 + b + 1;
            if (a % 2 == 0 || b % 2 == 0) ans--;
        } else {
            ans = (a + 1) * 2 + (b + 1) * 2 - 2 * (gcd(a, b) + 1);
            if (a % 2 == 0 || b % 2 == 0) ans--;
        }
        System.out.println(ans);
    }
}

def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)

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

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

算法及复杂度

  • 算法：数学计算 + 最大公约数()
  • 时间复杂度： - 主要来自于的计算
  • 空间复杂度： - 只需要存储几个整数变量