[NOI Online 2022 普及组] 数学游戏题解

[NOI Online 2022 普及组] 数学游戏（民间数据） - 洛谷

简化题意：

给定 $x, z$ 求是否存在满足条件 $z = x \times y \times gcd (x, y)$ 的 $y$ ，如果存在请输出，如果不存在输出 $- 1$ 。

输麻了，md 普及比提高还难。

考虑设 $d = gcd (x, y)$ 那么 $x = k_{x} d, y = k_{y} d, z = k_{x} k_{y} d^{3}$ 。

考虑我们最终要求的东西就是 $k_{y} d$ 考虑用根据三元方程组肯定是可以表示出的，考虑用已知量来表示未知， $k_{y} d = \frac{z}{x d}$ ，那么本质上我们只要求出 $d$ 就行了，考虑到我们可以通过 $gcd$ 的条件进行迭代，因为 $gcd (k_{x}, k_{y}) = 1$ 考虑通过这个性质构造出与 $d$ 有关的式子。

发现 $gcd (x, y) = gcd (k_{x} d, k_{y} d)$ ，将 $k_{y} d = \frac{z}{x d}$ 带入可以得到 $gcd (x, \frac{z}{x d}) = d$ 。

发现右边只是多了一个 $\frac{1}{d}$ ，考虑这个东西是 $k_{y} d \to \frac{z}{x d}$ 的，所以让其变成 $k_{y} d^{2}$ ，但是这样不能直接变换，发现 $k_{x}, k_{y}$ 对我们的答案一点影响都没有，所以左边只要也出现一个 $d^{2}$ 即可。