Codeforces Round #680 C. Division（分解质因子）

本文主要是介绍Codeforces Round #680 C. Division（分解质因子），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

C. Division

题目传送门：

Division

题目大意：

给你两个整数p和q，找出最大的x，使得p%x==0&&x%q ! = 0。

思路：

首先分类讨论：
1.如果p%q != 0，那么显然x=p

2.如果p=q，那么找到p的最小质因子k，x=p/k

3.p%q=0&&p!=q。
p%q=0说明q分解质因子后，每个质因子在p中必然存在且q中每个质因子的数量必然小于等于这个质因子在p中的数量。那么我们枚举q中的质因子，将q中的质因子ai的数量记做num1，p中质因子ai的数量记做num2,那么找到最小的pow( ai , num2-num1+1 )即可，记做minn。那么x=p/minn。

AC Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e9;
int t;
LL p,q;
LL quick_pow(LL a,LL b)
{LL res=1;while(b){if(b%2) res=res*a;b=b/2;a=a*a;}return res;
}
int main()
{scanf("%d",&t);while(t--){scanf("%lld%lld",&p,&q);if(p%q!=0) printf("%lld\n",p);else{if(p==q){int idx=0;for(int i=2;i*i<=p;i++){if(p%i==0){idx=i;break;} }if(idx==0) printf("1\n");else printf("%lld\n",p/idx);}else{LL k=p;LL res=1e18;LL idx=2;while(idx*idx<=q){if(q%idx!=0){idx++;continue;}LL cnt1=0,cnt2=0;while(q%idx==0){q=q/idx;cnt2++;}while(p%idx==0){p=p/idx;cnt1++;}res=min(res,quick_pow(idx,cnt1-cnt2+1));idx++;}if(q>1){LL cnt2=1,cnt1=0;while(p%q==0){cnt1++;p=p/q;}res=min(res,quick_pow(q,cnt1-cnt2+1));}printf("%lld\n",k/res);}}}//system("pause");return 0;
}