提交记录：https://www.luogu.com.cn/record/72440778

我这段代码本来是想骗90pts的，在本地一些小样例都跑过了，但在洛谷上提交后却爆零（全部数据都RE，还TLE了一个点），求大佬看看哪里有问题，为什么会RE

code：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fir first
#define sec second
const ll maxn=1e6;
ll t,x,z,vis[maxn+10],p[maxn+10],cnt,n,ans,a[maxn+10],flag;
pair<ll,ll>c[maxn+10];
ll ksm(ll x,ll p)
{
    ll base=x;
    ll ans=1;
    while(p)
    {
        if(p&1)ans*=base;
        p>>=1;
        base*=base;
    }
    return ans;
}
ll gcd(ll a,ll b)
{
	if(b==0)return a;
	return gcd(b,a%b);
}
void prime()
{
    for(ll i=2;i<=maxn;i++)
    {
        if(vis[i]==0)
            p[++cnt]=i;
        for(ll j=1;j<=cnt&&i*p[j]<=maxn;j++)
            vis[i*p[j]]=1;
    }
}
void get(ll x)
{
	n=0;
	for(ll i=1;i<=cnt&&x!=1;i++)
		if(x%p[i]==0)
		{
			n++;
			c[n].fir=i;
			while(x%p[i]==0)x/=p[i],c[n].sec++;
		}
} 
void dfs(ll id)
{
	if(flag)return;
	if(id>n)
	{
		ll g=1;
		for(ll i=1;i<=n;i++)g*=ksm(p[c[i].fir],a[i]);
//		for(ll i=1;i<=n;i++)cout<<a[i]<<" "<<c[i].fir<<" "<<c[i].sec<<endl;
//		cout<<g<<endl<<endl;
		ll y=z/x;
		if(y%g)return;
		y/=g;
		if(gcd(x,y)==g)
		{
			ans=y;
			flag=1;
		}
		return;
	}
	for(ll i=0;i<=c[id].sec;i++)
	{
//		cout<<"!!!"<<n<<" "<<id<<" "<<i<<endl;
		a[id]=i;
		dfs(id+1);
	}
}
void solve()
{
	cin>>x>>z;
	get(x);
	ans=-1;
	flag=0;
	dfs(1);
	cout<<ans<<endl;
}
int main()
{
//	freopen("math.in","r",stdin);
//	freopen("math.out","w",stdout);
	prime();
	cin>>t;
	while(t--)solve();
	return 0;
} 

思路：对$x$分解质因数，然后暴力枚举$x$的所有因数作为$gcd(x,y)$，然后判断$y$是否合法，复杂度$O(tlogx)$左右吧（可能，不太确定，但个人感觉不会RE）