CF1444A

Solution:

看到这道题，很容易想到朴素算法所以这里不在赘述。在看到题面中 (p) 和 (q) 的数据范围的差距后，可以想出，我们此时不能将 (p) 分解质因数，而应该将 (q) 分解质因数。另外，显然如果 (q mid p) 那么答案就是 (p) 。考虑如何处理 (qmid p) 的情况。因为 (q) 可以分解为 (q=prodlimits_{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
",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
",p/t);
    }
    return 0;
}