思路
首先特判特殊情况，若 \(p_i\) 本身不可被 \(q_i\) 整除，那么 \(x_i\) 就直接取 \(p_i\) 最大。
否则的话，\(p_i=q_i\times k\)。所以 \(q\) 的质因数，\(p\) 都有，并且数量一定大于等于 \(q\) 的这个质因数的数量。
那么如果 \(x_i\) 的某个质因数个数小于 \(q_i\) 的话，\(x_i\) 就不能被 \(q_i\) 整除。
其他的质因数个数就可以取 \(p_i\) 的。
所以我们先记录 \(p_i\) 到 \(a\)，然后直接枚举 \(q_i\) 的质因数，再然后除以 \(p_i\) 所有的这个质因数的积，再乘以 \(q_i\) 所有的这个质因数的积，再除以这个质因数，这样就得到了一个解，最后取所有解的最大值即可。
AC code
#include<bits/stdc++.h>
using namespace std;
int T;
long long a,b,ans,aa;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%lld%lld",&a,&b),ans=0,aa=a;
if(a%b){printf("%lld\n",a);continue;}
for(long long i=2;i*i<=b;++i)
{
if(b%i==0)
{
long long t2=1;
while(a%i==0) a/=i,t2*=i;
while(b%i==0) b/=i,t2/=i;
ans=max(ans,aa/t2/i);
}
}
if(b>1)
{
long long t2=1;
while(a%b==0) a/=b,t2*=b;
ans=max(ans,aa/t2);
}
printf("%lld\n",ans);
}
}