题解
由题易得,当\(p<q\)或\(p\%q\not=0\)时\(x=p\)。
其他情况:先使\(x=p\)
将\(p\)分解为\(k_1^{n_1}\cdot k_2^{n_2}\cdot k_3^{n_3}...\cdot k_m^{n_m}\),若将\(k\)中任意一个满足\(k_i^{n_i}|p\)的\(k_i\),使\(x\)中\(k_i\)的幂数\(\le n_i\),则\(x\%q\not=0\)。因此可以枚举\(k_i\),求出最大的\(x\)即可。
AC代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
int t,q,p;
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld",&p,&q);
if(p<q || p%q) {printf("%lld\n",p); continue;}
int qwq=0,qaq,qoq=p,quq,ans=0;
while(p%q==0) {qwq++; p/=q;}
for(int i=2;i*i<=q;i++)
{
if(q%i==0)
{
quq=1;
while(q%i==0) {q/=i; quq*=i;}
qaq=qoq;
while(qaq%quq==0) qaq/=quq;
while(qaq%quq!=0) qaq*=i;
ans=max(ans,qaq/i);
}
}
if(q>1)
{
qaq=qoq;
while(qaq%q==0) qaq/=q;
ans=max(ans,qaq);
}
printf("%lld\n",ans);
}
return 0;
}