昆明学校网站设计公司,企业网站源码百度网盘下载,seo网站优化服务合同,华为手机网站建设策划方案论文数学游戏 题目描述 Kri 喜欢玩数字游戏。 一天#xff0c;他在草稿纸上写下了 ttt 对正整数 (x,y)(x,y)(x,y)#xff0c;并对于每一对正整数计算出了 zxygcd(x,y)z x \times y \times \gcd(x,y)zxygcd(x,y)。 可是调皮的 Zay 找到了 Kri 的草稿纸#xff0c;并把每一组的… 数学游戏 题目描述 Kri 喜欢玩数字游戏。 一天他在草稿纸上写下了 ttt 对正整数 (x,y)(x,y)(x,y)并对于每一对正整数计算出了 zx×y×gcd(x,y)z x \times y \times \gcd(x,y)zx×y×gcd(x,y)。 可是调皮的 Zay 找到了 Kri 的草稿纸并把每一组的 yyy 都擦除了还可能改动了一些 zzz。 现在 Kri 想请你帮忙还原每一组的 yyy具体地对于每一组中的 xxx 和 zzz 你需要输出最小的正整数 yyy使得 zx×y×gcd(x,y)zx \times y \times \gcd(x,y)zx×y×gcd(x,y)。如果这样的 yyy 不存在也就是 Zay 一定改动了 zzz那么请输出 −1-1−1。 注 gcd(x,y)\gcd(x,y)gcd(x,y) 表示 xxx 和 yyy 的最大公约数也就是最大的正整数 ddd满足 ddd 既是 xxx 的约数又是 yyy 的约数。 输入格式 第一行一个整数 ttt表示有 ttt 对正整数 xxx 和 zzz。 接下来 ttt 行每行两个正整数 xxx 和 zzz含义见题目描述。 输出格式 对于每对数字输出一行如果不存在满足条件的正整数 yyy请输出 −1-1−1否则输出满足条件的最小正整数 yyy。 输入数据 1 1
10 240Copy 输出数据 1 12Copy 样例 1 解释
x×y×gcd(x,y)10×12×gcd(10,12)240x \times y \times \gcd(x,y) 10 \times 12 \times \gcd(10,12) 240x×y×gcd(x,y)10×12×gcd(10,12)240。 输入数据 2 3
5 30
4 8
11 11Copy 输出数据 2 6
-1
1Copy 附加样例
见样例目录下的 math3.in 和 math3.out 以及 math4.in 和 math4.out。
数据范围
对于 20%20\%20% 的数据t,x,z≤103t,x,z \le 10^3t,x,z≤103。
对于 40%40\%40% 的数据t≤103,x≤106,z≤109t \le 10^3,x \le 10^6,z \le 10^9t≤103,x≤106,z≤109。
对于另 30%30\%30% 的数据t≤104t \le 10^4t≤104。
对于另 20%20\%20% 的数据x≤106x \le 10^6x≤106。
对于 100%100\%100% 的数据1≤t≤5×105,1≤x≤109,1≤z2631 \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≤z263。 题意简述 给定正整数 x,zx,zx,z求满足 zx×y×gcd(x,y)zx\times y\times\gcd(x,y)zx×y×gcd(x,y) 的最小正整数 yyy若不存在输出 −1-1−1。 每个测试点有 ttt 次询问。 1≤t≤5×1051\leq t\leq 5\times 10^51≤t≤5×1051≤x≤1091\leq x\leq 10^91≤x≤1091≤z≤2631\leq z\leq 2^{63}1≤z≤263 题目分析 方法一 设 x,y,zx,y,zx,y,z 中分别含有 x1,y1,z1x_1,y_1,z_1x1,y1,z1 个素因子 222则 gcd(x,y)\gcd(x,y)gcd(x,y) 中含有 min(x1,y1)\min(x_1,y_1)min(x1,y1) 个素因子 222。 根据条件 zx×y×gcd(x,y)zx\times y\times\gcd(x,y)zx×y×gcd(x,y) 得 z1x1y1min(x1,y1)z_1x_1y_1\min(x_1,y_1)z1x1y1min(x1,y1)接着根据 x1x_1x1 和 y1y_1y1 的大小关系进行分类讨论 x1y1x_1y_1x1y1 此时 z1x12y1z_1x_12y_1z1x12y1且 x1y1⇔3x1z1x_1y_1\Leftrightarrow 3x_1z_1x1y1⇔3x1z1。注意 z1−x1z_1-x_1z1−x1 必须为偶数否则 y1y_1y1 会出现小数的情况。 x1≤y1x_1\leq y_1x1≤y1 此时 z12x1y1z_12x_1y_1z12x1y1且 x1≤y1⇔3x1≤z1x_1\leq y_1\Leftrightarrow 3x_1\leq z_1x1≤y1⇔3x1≤z1。 综上y1{z1−x12z1−x12−z12,3x1z1z1−2x1z1−x12−3x12,3x1≤z1z1−x12−min(3x1,z1)2y_1\begin{cases} \dfrac{z_1-x_1}2z_1-\dfrac{x_1}2-\dfrac{z_1}2,3x_1z_1\\ z_1-2x_1z_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−x1z1−2x1−2z1,z1−2x1z1−2x1−23x1,3x1z13x1≤z1z1−2x1−2min(3x1,z1)。 同理对于其他素因子也满足上文所述。 再将这个等式转化成 x,y,zx,y,zx,y,z 的形式 yzx÷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)} yx z÷gcd(x3,z) xz÷gcd(xz,x2) 方法二 令 ggcd(x,y)g\gcd(x,y)ggcd(x,y)得 zxyg⇒zxyg⇒zxyg×g2zxyg \Rightarrow\dfrac zxyg \Rightarrow\dfrac zx\dfrac yg\times g^2zxyg⇒xzyg⇒xzgy×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⇒ggcd(zx,x2)⇒yzx÷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\\ \Rightarrowg\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]g2ggcd(xz,x2) ⇒yxz÷gcd(xz,x2) 根据上述两种方法均可证明 yzx÷gcd(zx,x2)y\dfrac zx\div\sqrt{\gcd\left(\dfrac zx,x^2\right)}yxz÷gcd(xz,x2) 故直接计算此式即可。 时间复杂度 Θ(tlogx2)\Theta(t\log x^2)Θ(tlogx2)。注意计算 gcd\gcdgcd 的时间复杂度
