题解 CF1444A 【Division】

阅读体验更佳：[点这里](https://www.cnblogs.com/acceptedzhs/p/13912693.html) 题意：求最大的正整数 $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: ```cpp #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; } ```