CF1444A Division

#include<bits/stdc++.h>
#define ll long long
#define fp(i,a,b) for(int i=a;i<=b;i++)
#define sfp(i,a,b) for(int i=a;i<b;i++)
const ll N = 1e6+10;
using namespace std;

ll t;
ll p,q,cnt;
ll a[N],cnt1[N],cnt2[N];
void solve()
{
    cin>>p>>q;
    if(p%q!=0) cout<<p<<endl;
    else
    {
        cnt=0;
        ll b=sqrt(q);
        ll  P=p;
        //求q的质因数用a[]存起来，用cnt1存含有的个数
        fp(i,2,b)
        {
            if(q%i==0) a[++cnt]=i;
            while(q%i==0)
            {
                cnt1[cnt]++;
                q/=i;
            }
        }
        if(q>1)    //如果q本身就是质数
        {
            a[++cnt]=q;
            cnt1[cnt]=1;
        }
        //OVER
        fp(i,1,cnt)
        {
            while(p%a[i]==0)
            {
                cnt2[i]++;
                p/=a[i];
            }
        }
        ll ans=0;
        fp(i,1,cnt)
        {
            ll c=cnt2[i]-cnt1[i]+1;
            ll sum=1;
            for(int j=1;j<=c;j++) sum*=a[i];
            //sum=pow(a[i],c);
            ans=max(ans,P/sum);
        }
        cout<<ans<<endl;
        fp(i,1,cnt) cnt1[i]=0,cnt2[i]=0;
    }
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin>>t;
    while(t--) solve();
}

求数的质因数打方法在代码里面（注释）

该题的思路是找当p%q==0时，也就是q为p一个因子时，p中其他因子，且不能被q整除的最大值。

先将q拆除质因数表示的形式 如12=2_2_3(两个2和一个3),由于q为p因数，故p也含有这些质因数，将相同质因数的个数相减+1去枚举求出最大的因子。

P = 12 = 2 * 2 * 3 , Q = 6 = 2 * 3 ， p2 - q2 + 1 = 2 , 2 * 2=4 有点抽象