B3727

一扶苏一 · 2018-10-11 18:00:53 · 题解

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

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。

本题无视频题解。