暴力做法 因为$x*y*gcd(x,y)=z$ 那么$y*gcd(x,y)=z/x$,然后从1枚举到该值，找到第一个满足的y输出，可以拿到部分分。

进阶优化： y肯定是$z/x$的因子，在根号$z/x$范围内枚举可以更快一些，能多拿一些分。

满分做法： 可以看到z是$2^{63}$次方，而gcd算法也是log时间，同时还有$5×10^5$次方询问 容易想到是$O(qlogz)$的时间复杂度解决此问题 因此就注定了该题是需要$O(1)$的时间推导出y的值。

下面给出推导： 设$gcd(x,y)=d$,d为正整数。则$x$可以写成$m*d,y$可以写成$n*d$.$(m,n!=0)$且$gcd(n,m)=1$ 则$z=x*y*gcd(x,y)=m*d*n*d*d=mnd^3$

$z/x=n*d^2$

由于$gcd(n,m)=1$,根据最大公约数性质可以得到

$gcd(n,m^2)=1$

给$n$和$m^2$都乘以$d$平方得到$gcd(d*d*n,d*m*d*m)=d*d$ 结合$z/x=nd^2$ 既$gcd(z/x,x*x)=d*d$ 所以$d=sqrt(gcd(z/x,x*x))$ 根据$z=x*y*gcd(x,y),y=z/x/d$ 推导结束 根据此结论直接求$y$，求下来的$y$如若符合要求，则直接输出，否则输出-1

d = sqrtl(gcd(x * x, z / x));
y = z / x / d;
if (z == x * y * d && gcd(x, y) == d)
{
    cout << y << "\n";
    flag = true;
    continue;
}
if (!flag)
    cout << -1 << "\n";

#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef long long i64;
typedef unsigned int       u32;
typedef unsigned long long u64;
u64 gcd(u64 x,u64 y){return x==0?y:gcd(y%x,x);}
u64 mul(u64 x,u64 y,u64 m){
    u64 r=0; while(y){
        if(y&1) r=(r+x)%m; y>>=1,x=(x+x)%m;
    }
    return r;
}
int main(){
    int T; scanf("%d",&T); up(1,T,TT){
        u64 x,y,z,t,u; scanf("%llu%llu",&x,&z);
        u=mul(mul(x,x,z),x,z),t=sqrtl((long double)x*gcd(z,u)+0.5),y=z/t;
        if(z!=x*y*gcd(x,y)) puts("-1");
        else printf("%llu\n",y);
    }
    return 0;
}

非满分做法就不说了，太简单了。

首先观察数据规模得必须在 $O(log_2 n)$ 时间内计算单个问题。 $O(log_2 n)$ 的数学函数有哪些呢？有 $\texttt{gcd}$，有 $\texttt{sqrt}$。

接着要处理式子 $z=xy\times\gcd(x,y)$ 根据经验，数学题遇到 $\gcd(x,y)$ 就应该改成 $\gcd(nd,md)$ 的形式。 其中 $\gcd(x,y)=d$，$x=nd$，$y=md$。 改写后得 $z=nmd^3$，$\dfrac{z}{x}=md^2$。

然后可以去想：$d$ 到底等于多少？ 想知道 $d$ 的值，可以把 $\gcd(nd,md)$ 的凑成只包含已知数的式子。 那我们就可以去凑。

根据 $\dfrac{z}{x}=md^2$，考虑将 $md$ 凑成 $md^2$。 显然，$\gcd(n^2,m)=1$，所以 $\gcd(n^2d^2,md^2)=d^2$，$\sqrt{\gcd(n^2d^2,md^2)}=d$。 我们成功凑成了 $md^2$，还意外发现 $n^2d^2=x^2$，式子只包含已知数了。 最后根据 $z=xy\times\gcd(x,y)$，得出 $y=\dfrac{z}{xd}$。

最后注意，由于 $z<2^{63}$，所以要开 $\texttt{unsigned long long}$。 （虽然不开也能过，但这是因为数据太水，而不是代码本身正确。）

关键代码：

unsigned long long x, y, z;
cin >> x >> z;
y = z / x / (unsigned long long)(sqrtl(__gcd(z / x, x * x)) + 0.5);
if (x * y * __gcd(x, y) == z)
    cout << y << endl;
else
    cout << "-1\n";

👍 写题解请注意

鼓励大家写题解，但注意题解格式。

题解一定要有思路解析或代码注释，能否让别人理解你的思路

也是你的能力的检验，不要只放无意义的代码给大家复制，那就失去了做题的初心。

给代码两端加上这个会舒服一些

```cpp

你的代码

```

</span>

这个点在键盘的左上角tab上面那个键，注意切换输入法

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;//这是一个注释
    return 0;
}

Copy

Copy

请注意严禁抄袭题解，写题解不要只放代码，需加上你的思路或代码注释。

抄袭题解一经发现直接取消成绩。

题解被删除的可能

1. 代码不符合格式规范
2. 没有思路讲解或者没有注释，
3. 无意义的题解

大家携手共同维护一个良好的编程环境，如果一经发现，多次作乱。可能会被管理员拉黑，请注意，一旦拉黑即失去登陆资格。

写题解请注意

鼓励大家写题解，但注意题解格式。

题解一定要有思路解析或代码注释，能否让别人理解你的思路

也是你的能力的检验，不要只放无意义的代码给大家复制，那就失去了做题的初心。

给代码两端加上这个会舒服一些

```cpp

你的代码

```

</span>

这个点在键盘的左上角tab上面那个键，注意切换输入法

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;//这是一个注释
    return 0;
}

Copy

请注意严禁抄袭题解，写题解不要只放代码，需加上你的思路或代码注释。

抄袭题解一经发现直接取消成绩。

题解被删除的可能

1. 代码不符合格式规范
2. 没有思路讲解或者没有注释，
3. 无意义的题解

大家携手共同维护一个良好的编程环境，如果一经发现，多次作乱。可能会被管理员拉黑，请注意，一旦拉黑即失去登陆资格。

写题解请注意

鼓励大家写题解，但注意题解格式。

题解一定要有思路解析或代码注释，能否让别人理解你的思路

也是你的能力的检验，不要只放无意义的代码给大家复制，那就失去了做题的初心。

给代码两端加上这个会舒服一些

```cpp

你的代码

```

</span>

这个点在键盘的左上角tab上面那个键，注意切换输入法

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;//这是一个注释
    return 0;
}

请注意严禁抄袭题解，写题解不要只放代码，需加上你的思路或代码注释。

抄袭题解一经发现直接取消成绩。

题解被删除的可能

1. 代码不符合格式规范
2. 没有思路讲解或者没有注释，
3. 无意义的题解

大家携手共同维护一个良好的编程环境，如果一经发现，多次作乱。可能会被管理员拉黑，请注意，一旦拉黑即失去登陆资格。