1 条题解
-
0
题意简述
-
给定正整数 ,求满足 的最小正整数 ,若不存在,输出 。
-
每个测试点有 次询问。
-
,,
题目分析
方法一
设 中分别含有 个素因子 ,则 中含有 个素因子 。
根据条件 得 ,接着根据 和 的大小关系进行分类讨论:
-
此时 ,且 。注意 必须为偶数,否则 会出现小数的情况。 -
此时 ,且 。
综上,$y_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)}2$。
同理,对于其他素因子,也满足上文所述。
再将这个等式转化成 的形式:
$$y=\dfrac z{\sqrt{x}}\div\sqrt{\gcd(x^3,z)}=\dfrac zx\div\sqrt{\gcd\left(\dfrac zx,x^2\right)} $$方法二
令 ,得
$$z=xyg \Rightarrow\dfrac zx=yg \Rightarrow\dfrac zx=\dfrac yg\times g^2$$根据最大公约数性质,我们有 ,可得
$$\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}$$根据上述两种方法,均可证明 $y=\dfrac zx\div\sqrt{\gcd\left(\dfrac zx,x^2\right)}$,故直接计算此式即可。
时间复杂度 。(注意计算 的时间复杂度)
-
- 1
信息
- ID
- 245
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 68
- 已通过
- 7
- 上传者