Codeforces 1445C. Division

题目大意

• 给出$p,q$，求最大的$x$使得$x$能被$p$整除但$q$不能被$x$整除。
• $p\le 10^{18}$，$2\le q\le 10^9$

题解

• 可以先令$x=p$，若不满足第二个条件则不断把$x$改小，
• 显然为了满足$x$仍旧是$p$的约数，每次要让$x$除以某个数，
• 为了让第二个条件成立，需要$q$分解质因数后某一项$c^k$在$x$中只有$c^{k^{\prime }}(k^{\prime }<k)$，
• 而且为了$x$尽可能大，所以只需要某一个质因数满足即可，
• 那么枚举$q$的每个质因数，把$x$一直除以它直到条件成立，在所有这样操作后的$x$中取最大值。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
int main() {
int tn;
scanf("%d", &tn);
while(tn--) {
ll p, q, i;
scanf("%lld%lld", &p, &q);
ll Q = q;
ll t = 0;
for(i = 2; i * i <= q; i++) if(q % i == 0) {
while(q % i == 0) q /= i;
ll ss = p, l = 1;
while(ss % Q == 0 && ss % i == 0) ss /= i, l *= i;
t = max(t, ss);
}
if(q > 1) {
ll ss = p, l = 1;
while(ss % Q == 0 && ss % q == 0) ss /= q, l *= q;
t = max(t, ss);
}
printf("%lldn", t);
}
return 0;
}

最后

以上就是明理白云为你收集整理的Codeforces 1445C. Division（分解质因数）Codeforces 1445C. Division的全部内容，希望文章能够帮你解决Codeforces 1445C. Division（分解质因数）Codeforces 1445C. Division所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。