首页 > 试题广场 >

墙壁划线

[编程题]墙壁划线
  • 热度指数:600 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解

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


输入描述:

一行四个正整数,墙壁的长有块瓷砖,宽有块瓷砖,瓷砖的长,宽



输出描述:

一个正整数,交点数目。

示例1

输入

2 2 1 1

输出

5

说明

产生5个交点如图所示:

示例2

输入

2 3 2 1

输出

9

说明

产生9个交点如图所示:


备注:
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long a = scanner.nextInt();
        long b = scanner.nextInt();
        long x = scanner.nextInt();
        long y = scanner.nextInt();
                
        long gcdXY = gcd(x, y);
        x /= gcdXY;
        y /= gcdXY;
        long ans = 0;
        if (a == b) {
            ans = a + b + 2;
            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);
    }

    private static long gcd(long a, long b) {
        while (b != 0) {
            long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

发表于 2025-04-07 14:17:46 回复(0)