菜鸡一个。

题解 CF1444A 【Division】

2020-11-03 07:49:52


阅读体验更佳:点这里

题意:求最大的正整数 $x$ ,使 $x \mid p$ 且 $q \nmid x$ 。

首先,当 $q \nmid p$ ,显然取 $x=p$ 是最优解。

现在,我们考虑 $q \mid p$ 的情况。

考虑对 $q$ 分解质因数,设 $q=p_1^{a_1} \times p_2^{a_2}\times \cdots \times p_n^{a_n}$ 。

那么,$x$ 不为 $q$ 的倍数,当且仅当 $\exists i$,使得 $x$ 分解质因数后 $p_i$ 的次数 $< a_i$ 。

我们可以枚举每个 $p_i$ ,使 $x$ 分解质因数后 $p_i$ 的次数为 $a_i-1$ ,其他全部拉满即可。

也就是说,设 $t$ 是 $p$ 被 $p_i$ 除尽后剩下的数,则最优解是 $p_i^{a_i-1} \times t$ 。

最后在这些备选最优解中取 $\max$ 即可。

Code:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=100010;
ll T,p,q,pr[N],cnt,vis[N];
void pre(int lim){
    for(int i=2;i<=lim;i++){
        if(!vis[i]){
            vis[i]=1;pr[++cnt]=i;
            for(int j=i;j<=lim/i;j++) vis[i*j]=1;
        }   
    }
}

int main(){
    scanf("%d",&T);pre(N-1);
    while(T--){
        scanf("%lld%lld",&p,&q);
        if(p%q!=0) cout<<p<<endl;
        else{
            ll ans=1,tmp=q;
            for(int i=1;i<=cnt;i++){
                ll cs=0,res=1;
                while(tmp%pr[i]==0) tmp/=pr[i],cs++,res*=pr[i];
                if(!cs) continue;//cs即为上文提到的a_i
                res/=pr[i];//res=pr[i]^(a_i-1)
                if(p%res==0){
                    ll tmp1=p;while(tmp1%pr[i]==0) tmp1/=pr[i];
                    ans=max(ans,res*tmp1);
                }   
            }
            if(tmp>1){//如果tmp还有残余,说明tmp本身是个质数
                ll res=1;
                //res肯定为1,不用算了
                if(p%res==0){
                    ll tmp1=p;while(tmp1%tmp==0) tmp1/=tmp;
                    ans=max(ans,res*tmp1);
                }
            }
            cout<<ans<<endl;
        }
    }
    return 0;
}