Problem

Luogu

Solution

对于这道题，你先思考一件事情，两个数的最大公约数和两个数有什么关系呢？

设 d 为两数的最大公约数，那么 d 可以被两数所除。

且两数与 d 相除，其商一定互质，为什么呢？如果不互质，那么就不是最大公约数了。

我们现在先设 a 和 b 为两个商，即 x=d \times a 和 y=d \times b。

a 和 b 互质，现在我们可以知道 z=a \times b \times d^3。

然后我们可以知道 \frac{z}{x} = y \times gcd(x,y) = b \times d^2。

为了求出这个 d，我们还需要知道一个数，包含 d，且能用一种方式解出来。

前面我们说过，a 和 b 互质，所以我们可以用 gcd(\frac{z}{x}, x^2)=gcd(b \times d^2,a^2 \times d^2) 求得。

为什么这样求得 d 就可以知道 y 呢，因为这样就可以保证 d 尽可能最大，然后 y 最小了。

d=\sqrt{gcd(\frac{z}{x}, x^2)}

y=\frac{z}{x \times d}