首页 > 试题广场 >

墙壁划线

[编程题]墙壁划线
  • 热度指数：389 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}一面矩形墙由 a\times b 块完全一致的瓷砖铺成，每块瓷砖尺寸为 x\times y。墙的左上角坐标记为 (0,0)，右下角为 (a\!\cdot\!x,\,b\!\cdot\!y)。

\hspace{15pt}现从：
\hspace{23pt}\bullet\, 左上角连到右下角；
\hspace{23pt}\bullet\, 右上角连到左下角
\hspace{15pt}各画一条直线。求两条直线与所有瓷砖边界线（即位于 x=ix 或 y=jy\;(i,j\in\mathbb Z) 的网格线）形成的交点总数。

输入描述:
\hspace{15pt}一行输入四个正整数 a,b,x,y\;(1\leqq a,b,x,y\leqq 10^{9})。


输出描述:
\hspace{15pt}输出一个整数，表示交点总数。
示例1

输入

2 2 1 1

输出

5

说明

产生5个交点如图所示：
示例2

输入

2 3 2 1

输出

9

说明

产生9个交点如图所示：

算法知识视频讲解
开通博客
头像 冷艳的西红柿刷牛客
发表于 2025-10-22 16:12:19
#include <iostream> using namespace std; int gcd(int a, int b) { if (a % b == 0) return b; return gcd(b, a % b); } //其实是数论的问题，题目之和a, b（a, 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Silencer76
发表于 2025-07-14 18:01:59
题目链接 墙壁划线 题目描述 一面矩形墙壁由 块完全一致的瓷砖铺成，每块瓷砖尺寸为 。现在从墙的左上角到右下角、右上角到左下角各画一条直线。 请求出这两条直线与所有瓷砖边界线（包括墙壁的边界）形成的交点总数。 输入: 一行输入四个正整数 。 输出: 输出一个整数，表示交点总数。 解题思路 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 丨阿伟丨
发表于 2025-08-29 09:55:18
题目链接 墙壁划线 题目描述 一面尺寸为 的矩形墙壁由 块尺寸为 的瓷砖铺成。现从墙的左上角到右下角、右上角到左下角各画一条直线。求这两条直线与所有瓷砖边界线形成的交点总数。 解题思路 这是一个几何计数问题，可以通过坐标法和数论知识解决。 简化问题 首先，一个关键的观察是，交点的数量只与瓷砖的 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

来自：2025年秋招-中国联...
难度：
0条回答 13浏览

热门推荐

相关试题

墙壁划线

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号