自动搬运

查看原文

来自洛谷，原作者为

	一扶苏一 休息结束。邮箱 yifusuyi@qq.com

搬运于2025-08-24 21:14:40，当前版本为作者最后更新于2018-10-11 18:00:53，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

[语言月赛202303] Hack Problem P 题解

Source & Knowledge

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

本题考查简单的语法易错点。

文字题解

题目大意

本题的题意是，要求你给出一组输入数据，使得题目中给出的求两数最小公倍数的程序输出错误的结果。

你的数据需要保证 $1 \leq x, y \leq 10^9$，两数的最小公倍数也不超过 $10^9$。

分析

代码中给出的公式是正确的：$\mathrm{lcm}(x,y) = \frac{x \times y}{\gcd(x, y)}$

但问题在于，代码先计算了 $x \times y$，然后再除以了两数的最大公约数。当 $x$ 和 $y$ 都很大时，计算 $x \times y$ 这一步时就已经超出了 int 的存储范围了，会得到错误的乘积，再除以 $\gcd(x, y)$ 的值自然也就错误了。

于是我们只需要构造两个很大的数，使得他们乘起来会爆 int，且最小公倍数不爆 int。

显然两个相同的数的最小公倍数是自身，所以给出两个 $10^9$ 是一个很好的选择。其他符合要求的数据也可以通过本题。

顺带一提，依本题题意，正确的计算 lcm 方法应该是 ans = x / __gcd(x, y) * y，这样可以保证运算过程中没有数超过 lcm。

视频题解

本题无视频题解。