自动搬运

查看原文

来自洛谷，原作者为

	Maxmilite **

搬运于2025-08-24 21:14:28，当前版本为作者最后更新于2023-01-05 20:24:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[语言月赛202301] 铺地毯 题解

Source & Knowledge

2023 年 1 月语言月赛，由洛谷网校入门计划/基础计划提供。

文字题解

题目大意

输入 $a, b, c$，判断能否使用边长为 $c$ 的正方形在「不进行裁切且两两不重叠」的前提下铺满长为 $a$ 宽为 $b$ 的矩形。

解析

容易发现，当且仅当 $a$ 与 $b$ 均能被 $c$ 整除时，我们才可以使用边长为 $c$ 的正方形在「不进行裁切且两两不重叠」的前提下铺满长为 $a$ 宽为 $b$ 的矩形。

如果 $a$ 或 $b$ 无法整除，容易发现如果想要铺满矩形，总会有正方形被裁切或两两重叠。

因此首先我们需要判断 $a$ 与 $b$ 能否均被 $c$ 整除，如果可以，容易发现需要的矩形个数为 $\dfrac{ab}{c ^ 2}$。

这里的一个坑点是，数据仅保证最终答案不超过 $10 ^ {18}$，而没有保证运算过程中的数值不超过 $10 ^ {18}$。这意味着，我们不仅要使用 long long，而且如果使用 long long a, b, c; ...; long long ans = a / c * b / c 这样先乘后除的算法，运算过程中可能会发生 long long 溢出。

不妨考虑 $a = 10 ^ {18}, b = 10 ^ {18}, c = 10 ^ 9$，显然最后的答案为 $10 ^ {18}$，然而先运算 $a \div c \times b$ 的结果为 $10 ^ {27}$，显然会造成 long long 溢出。

如果提交类似这样的程序，会得到 $70$ 分的成绩。

解决方法有很多，一种方法是使用 __int128，这里可以自行查阅相关资料。

另一种方法是使用 (a / c) * (b / c) 算式，首先运算 $\dfrac ac$ 和 $\dfrac bc$，得到结果后再相乘，这样即可保证运算过程中数值不超过 $10 ^ {18}$。

视频题解

完整代码请在视频中查看。