我不理解

这个代码是暴力 pollard-rho 的

#include<bits/stdc++.h>
#define int long long
#define lll __int128
using namespace std;

int x,z,tmp;

inline int qmi(int a,int b,int c)
{
	register int ans=1,res=a;
	while(b)
	{
		if(b&1) ans=(lll)ans*res%c;
		res=(lll)res*res%c;
        b>>=1;
	}
	return ans;
}

int prime[]={2,3,5,7,11,23,61};

bool mr(int x)
{
    if(x==2) return 1;
    if(x<2 || !(x&1)) return 0;
    int s=0,t=x-1;
    while(!(t&1))
    {
        ++s;
        t>>=1;
    }
    for(int i=0; i<7 && prime[i]<x; ++i)
    {
        int k,b=qmi(prime[i],t,x);
        for(int j=1; j<=s; ++j)
        {
            k=(lll)b*b%x;
            if(k==1 && b!=1 && b!=x-1)
            {
                return 0;
            }
            b=k;
        }
        if(b!=1) return 0;
    }
    return 1;
}

inline int gcd(int a,int b)
{
	if(!a) return b;
	if(!b) return a;
	int t=__builtin_ctzll(a|b),tmp;
	a>>=__builtin_ctzll(a);
	do
	{
		b>>=__builtin_ctzll(b);
        if(a>b) swap(a,b);
		b-=a;
	} while(b);
	return a<<t;
}

inline int f(const int &x,const int &c,const int &n)
{
    return ((lll)x*x+c)%n;
}

inline int big_rand(const int &x)
{
    return (rand()<<1^rand())<<30^(rand()<<15^rand())%x;
}

int ans;

int pri[10010],cnt;

inline void pr(int g)
{
	//if(gcd(z/x/g,x)==g) ans=min(ans,z/x/g);
	//if(gcd(z/x/(tmp/g),x)==g) ans=min(ans,z/x/(tmp/g));
	if(g==1) return;
	if(mr(g))
	{
		pri[++cnt]=g;
		return;
	}
	int c=big_rand(g),t1=big_rand(g),
        t2=f(t1,c,g),d=abs(t1-t2),gg=gcd(g,d);
	while(t1!=t2 && gg==1)
	{
		t1=f(t1,c,g),t2=f(t2,c,g),t2=f(t2,c,g),
        d=(t1>t2?t1:t2)-(t1<t2?t1:t2),gg=gcd(g,d);
	}
	pr(gg),pr(g/gg);
}

void dfs(int wz,int now)
{
	if(gcd(z/x/now,x)==now)
	{
		ans=min(ans,z/x/now);
	}
	if(wz==cnt+1) return;
	int cnt=0,ttmp=tmp;
	while(ttmp)
	{
		++cnt;
		ttmp/=pri[wz];
	}
	int nnow=now;
	for(int i=0; i<=cnt; ++i)
	{
		if(z/x%nnow) break;
		dfs(wz+1,nnow);
		nnow*=pri[wz];
	}
}

signed main()
{
	srand((unsigned)time(NULL));
	//freopen("math.in","r",stdin);
	//freopen("math.out","w",stdout);
	int t;
	scanf("%lld",&t);
	while(t--)
	{
		cnt=0;
		scanf("%lld%lld",&x,&z);
		tmp=gcd(x,z/x);
		pr(tmp);
		sort(pri+1,pri+cnt+1);
		cnt=unique(pri+1,pri+cnt+1)-pri-1;
		ans=9e18;
		dfs(1,1);
		printf("%lld\n",ans==9e18?-1:ans);
	}
	return 0;
}