NOIOLPJ2022B. 数学游戏 分析

数学游戏

题目描述

Kri 喜欢玩数字游戏。

一天，他在草稿纸上写下了 $t$ 对正整数 $(x,y)$，并对于每一对正整数计算出了 $z=x\times y\times \gcd (x,y)$。

可是调皮的 Zay 找到了 Kri 的草稿纸，并把每一组的 $y$ 都擦除了，还可能改动了一些 $z$。

现在 Kri 想请你帮忙还原每一组的 $y$，具体地，对于每一组中的 $x$ 和 $z$ ，你需要输出最小的正整数 $y$，使得 $z=x\times y\times \gcd (x,y)$。如果这样的 $y$ 不存在，也就是 Zay 一定改动了 $z$，那么请输出 $-1$。

注： $\gcd (x,y)$ 表示 $x$ 和 $y$ 的最大公约数，也就是最大的正整数 $d$，满足 $d$ 既是 $x$ 的约数，又是 $y$ 的约数。

输入格式

第一行一个整数 $t$，表示有 $t$ 对正整数 $x$ 和 $z$。

接下来 $t$ 行，每行两个正整数 $x$ 和 $z$，含义见题目描述。

输出格式

对于每对数字输出一行，如果不存在满足条件的正整数 $y$，请输出 $-1$，否则输出满足条件的最小正整数 $y$。

输入数据 1

1
10 240

Copy

输出数据 1

12

Copy

样例 1 解释

$x\times y\times \gcd (x,y)=10\times 12\times \gcd (10,12)=240$。

输入数据 2

3
5 30
4 8
11 11

Copy

输出数据 2

6
-1
1

Copy

附加样例

见样例目录下的 math3.in 和 math3.out ，以及 math4.in 和 math4.out。

数据范围

对于 $20\%$ 的数据，t,x,z≤103t,x,z \le 10^3t,x,z≤103。

对于 $40\%$ 的数据，t≤103,x≤106,z≤109t \le 10^3,x \le 10^6,z \le 10^9t≤103,x≤106,z≤109。

对于另 $30\%$ 的数据，t≤104t \le 10^4t≤104。

对于另 $20\%$ 的数据，x≤106x \le 10^6x≤106。

对于 $100\%$ 的数据，1≤t≤5×105,1≤x≤109,1≤z<2631 \le t \le 5 \times 10^5,1 \le x \le 10^9,1 \le z < 2^{63}1≤t≤5×105,1≤x≤109,1≤z<263。

题意简述

• 给定正整数 $x,z$，求满足 $z=x\times y\times \gcd (x,y)$ 的最小正整数 $y$，若不存在，输出 $-1$。

• 每个测试点有 $t$ 次询问。

• 1≤t≤5×1051\leq t\leq 5\times 10^51≤t≤5×105，1≤x≤1091\leq x\leq 10^91≤x≤109，1≤z≤2631\leq z\leq 2^{63}1≤z≤263

题目分析

方法一

设 $x,y,z$ 中分别含有 x1,y1,z1x_1,y_1,z_1x1​,y1​,z1​ 个素因子 $2$，则 $\gcd (x,y)$ 中含有 min⁡(x1,y1)\min(x_1,y_1)min(x1​,y1​) 个素因子 $2$。

根据条件 $z=x\times y\times \gcd (x,y)$ 得 z1=x1+y1+min⁡(x1,y1)z_1=x_1+y_1+\min(x_1,y_1)z1​=x1​+y1​+min(x1​,y1​)，接着根据 x1x_1x1​ 和 y1y_1y1​ 的大小关系进行分类讨论：

• x1>y1x_1>y_1x1​>y1​
  此时 z1=x1+2y1z_1=x_1+2y_1z1​=x1​+2y1​，且 x1>y1⇔3x1>z1x_1>y_1\Leftrightarrow 3x_1>z_1x1​>y1​⇔3x1​>z1​。注意 z1−x1z_1-x_1z1​−x1​ 必须为偶数，否则 y1y_1y1​ 会出现小数的情况。

• x1≤y1x_1\leq y_1x1​≤y1​
  此时 z1=2x1+y1z_1=2x_1+y_1z1​=2x1​+y1​，且 x1≤y1⇔3x1≤z1x_1\leq y_1\Leftrightarrow 3x_1\leq z_1x1​≤y1​⇔3x1​≤z1​。

综上，y1={z1−x12=z1−x12−z12,3x1>z1z1−2x1=z1−x12−3x12,3x1≤z1=z1−x12−min⁡(3x1,z1)2y_1=\begin{cases} \dfrac{z_1-x_1}2=z_1-\dfrac{x_1}2-\dfrac{z_1}2,&3x_1>z_1\\ z_1-2x_1=z_1-\dfrac{x_1}2-\dfrac{3x_1}2,&3x_1\leq z_1 \end{cases}=z_1-\dfrac{x_1}2-\dfrac{\min(3x_1,z_1)}2y1​=⎩ ⎨ ⎧​2z1​−x1​​=z1​−2x1​​−2z1​​,z1​−2x1​=z1​−2x1​​−23x1​​,​3x1​>z1​3x1​≤z1​​=z1​−2x1​​−2min(3x1​,z1​)​。

同理，对于其他素因子，也满足上文所述。

再将这个等式转化成 $x,y,z$ 的形式：

y=zx÷gcd⁡(x3,z)=zx÷gcd⁡(zx,x2)y=\dfrac z{\sqrt{x}}\div\sqrt{\gcd(x^3,z)}=\dfrac zx\div\sqrt{\gcd\left(\dfrac zx,x^2\right)} y=x ​z​÷gcd(x3,z) ​=xz​÷gcd(xz​,x2) ​

方法二

令 $g=\gcd (x,y)$，得

z=xyg⇒zx=yg⇒zx=yg×g2z=xyg \Rightarrow\dfrac zx=yg \Rightarrow\dfrac zx=\dfrac yg\times g^2z=xyg⇒xz​=yg⇒xz​=gy​×g2

根据最大公约数性质，我们有 gcd⁡(xg,yg)=1\gcd\left(\dfrac xg,\dfrac yg\right)=1gcd(gx​,gy​)=1，可得

gcd⁡(zx,x2)=gcd⁡[yg×g2,(xg)2×g2]=g2⇒g=gcd⁡(zx,x2)⇒y=zx÷gcd⁡(zx,x2)\begin{aligned} &\gcd\left(\dfrac zx,x^2\right)=\gcd\left[\dfrac yg\times g^2,\left(\dfrac xg\right)^2\times g^2\right]=g^2\\ \Rightarrow&g=\sqrt{\gcd\left(\dfrac zx,x^2\right)} \Rightarrow y=\dfrac zx\div\sqrt{\gcd\left(\dfrac zx,x^2\right)}\end{aligned}⇒​gcd(xz​,x2)=gcd[gy​×g2,(gx​)2×g2]=g2g=gcd(xz​,x2) ​⇒y=xz​÷gcd(xz​,x2) ​​

根据上述两种方法，均可证明 y=zx÷gcd⁡(zx,x2)y=\dfrac zx\div\sqrt{\gcd\left(\dfrac zx,x^2\right)}y=xz​÷gcd(xz​,x2) ​，故直接计算此式即可。

时间复杂度 Θ(tlog⁡x2)\Theta(t\log x^2)Θ(tlogx2)。（注意计算 $\gcd$ 的时间复杂度）