我要招人

去企业版

首页 > 试题广场 >

墙壁划线

[编程题]墙壁划线

热度指数：600 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

输入描述:

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

输出描述:

一个正整数，交点数目。

示例1

输入

2 2 1 1

输出

说明

产生5个交点如图所示：

示例2

输入

2 3 2 1

输出

说明

产生9个交点如图所示：

备注:

算法知识视频讲解

Java

上岸保佑

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)

小吴努力ing

import math

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

x //= math.gcd(x, y)

y //= math.gcd(x, y)

ans = (a + b + 2) if a == b else (a + 1) * 2 + (b + 1) * 2 - 2 * (math.gcd(a, b) + 1)

if a % 2 == 0 or b % 2 == 0:

ans -= 1

print(ans)

发表于 2025-04-19 12:40:34 回复(0)

C++

qusirn

#include <iostream>
#include <numeric>
using namespace std;

int main() {
    long long a, b, x, y;
    cin >> a >> b >> x >> y;

    long long d = gcd(a, b);
    long long pointsPerLine = a + b + 1 - d;
    long long totalPoints = 2 * pointsPerLine;

    if (a % 2 == 0 || b % 2 == 0) {
        totalPoints--;
    }

    cout << totalPoints << endl;

    return 0;
}

发表于 2025-07-01 15:06:23 回复(0)

一笑而过2222

发表于 2025-05-19 17:21:09 回复(1)

提交观点

问题信息

基础数学数论

上传者：turnsoul

难度：

4条回答 19收藏 416浏览

墙壁划线

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

备注:

问题信息

热门推荐

相关试题