Solution:
看到这道题,很容易想到朴素算法所以这里不在赘述。在看到题面中 \(p\) 和 \(q\) 的数据范围的差距后,可以想出,我们此时不能将 \(p\) 分解质因数,而应该将 \(q\) 分解质因数。另外,显然如果 \(q\nmid p\) 那么答案就是 \(p\) 。考虑如何处理 \(q\mid p\) 的情况。因为 \(q\) 可以分解为 \(q=\prod\limits_{i=1}^s pri[i]^{c[i]}\) 我们只需要让最后的答案中有一个质因子为 \(pri[i]^{c[i]-1}\) 即可达成题目条件,所以最后统计答案是,逐个取 \(\min\) 即可。
Code:
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
int x=0,f=1;char c=getchar();
while(c<'0' || c>'9'){if(c=='-') f=0;c=getchar();}
while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return f?x:-x;
}
const int N=4e5;
int qpow(int a,int x)
{
int res=1;
while(x)
{
if(x&1) res=res*a;
a*=a;
x>>=1;
}
return res;
}
int pri[N],vis[N],cnt;
void prime()
{
for(int i=2;i<N;i++)
{
if(!vis[i]) pri[++cnt]=i;
for(int j=1;j<=cnt;j++)
{
if(pri[j]*i>=N) break;
vis[pri[j]*i]=1;
if(i%pri[j]==0) break;
}
}
}
int T,p,q,num[N],ti[N],s;
signed main()
{
prime();
T=read();
while(T--)
{
p=read(),q=read();
if(p%q){printf("%lld\n",p);continue;}
s=0;
for(int i=1;i<=cnt && pri[i]<=q;i++)
{
if(q%pri[i]==0)
{
num[++s]=pri[i];
ti[s]=0;
while(q%pri[i]==0)
{
ti[s]++;
q/=pri[i];
}
}
}
if(q!=1)
{
num[++s]=q;
ti[s]=1;
}
int x,t=p,tmp;
for(int i=1;i<=s;i++)
{
x=p; tmp=0;
while(x%num[i]==0)
{
x/=num[i];
tmp++;
}
t=min(t,qpow(num[i],tmp-ti[i]+1));
}
printf("%lld\n",p/t);
}
return 0;
}