【CF1445C】Divison 题解
数论 质因数分解
题意简介
给出两个正整数 p 和 q，要求一个最大的 x 使 p 可被 x 整除，而 q 不可被 x 整除。
其中，\(1 \leq p \leq 10^{18} ; 2 \leq q \leq 10^9\)。
思路分析
对于 \(p\mod q \neq 0\) 的情形，显然 x 最大为 p。
至于 \(p \equiv 0 \mod q\) 的情形，可以这样考虑：
首先，我们不难发现 p 必然包含 q 的所有质因数，且 p 质因数分解后每个质因数的指数必定大于等于 q 的。
现在，我们希望 \(x \mod q \neq 0\) 。要求 x 最大，所以我们希望这个 x 可以尽可能地接近 p。
我们记：
\(p = A_1^{d_1} \times A_2^{d_2} \times … \times A_n^{d_n} \times R\)
\(q = A_1^{c_1} \times A_2^{c_2} \times … \times A_n^{c_n}\)
显然地，要使 x 尽可能大，我们只需要通过除去某个数，把 p 的某个质因数的指数 \(d_i\) 调到恰好比 \(c_i\) 小就行了。
所以，我们只需要对 q 做质因数分解，顺便求出 \(c_i,d_i\) 。
然后枚举每个质因数，找到最小的 \(A_i^{d_i-c_1+1}\) ，答案就是 p 除以它了。
代码库
#include <cstdio>
#include <cstring>
typedef long long ll;
const int N=1e5;
ll a[N],cc,cq[N],cp[N],aq[N],ap[N];
int main(){
ll t; scanf("%lld",&t);
while(t--){
ll p,q,p1,q1; scanf("%lld%lld",&p,&q);
if(p%q!=0){
printf("%lld\n",p);
continue;
}
p1=p; q1=q; cc=0;
for(int i=2;i*i<=q;i++){
if(q1%i==0){
//记得初始化
a[++cc]=i; cq[cc]=cp[cc]=0; ap[cc]=aq[cc]=1;
while(q1%i==0) q1/=i,cq[cc]++,aq[cc]*=i;
while(p1%i==0) p1/=i,cp[cc]++,ap[cc]*=i;
}
}
//不要忘了这一步
if(q1>1){
a[++cc]=q1;
cq[cc]=cp[cc]=0; ap[cc]=aq[cc]=1;
while(q1%a[cc]==0) q1/=a[cc],cq[cc]++,aq[cc]*=a[cc];
while(p1%a[cc]==0) p1/=a[cc],cp[cc]++,ap[cc]*=a[cc];
}
ll minn=1e18;
for(int i=1;i<=cc;i++){
if(ap[i]/(aq[i]/a[i])<minn) minn=ap[i]/(aq[i]/a[i]);
}
printf("%lld\n",p/minn);
}
return 0;
}
版权声明：本文为Qing-LKY原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。