[cf] 680 div1 A. Division

前言

t a g : tag : tag: 数学 质因数分解 暴力 *1500(不感觉是1500 传送门 :

题意 : 给定 p , q p,q p,q,寻找一个最大的 x x x使得

p % x = = 0 , x % q ! = 0 p\%x ==0 ,x\%q!=0 p%x==0,x%q!=0

范围 : p ≤ 1 0 18 , q ≤ 1 0 9 p\le10^{18},q\le10^9 p≤1018,q≤109

思路 : 首先 显然的 p % q ≠ 0 p\%q\neq0 p%q​=0的话,那么答案就是 p p p

其次对于这种题一开始就想到的是质因数分解

但是对 p p p进行质因数分解显然失智

因此我们考虑对 q q q进行质因数分解

我们发现如果 p % x = = 0 p\%x==0 p%x==0那么 x x x质因数分解的结果一定是 p p p分解的子集

同理 q q q质因数分解的结果也是 p p p分解结果的子集

因此对于 x % q ≠ 0 x\%q\neq0 x%q​=0,那么肯定某一个质因子, x x x的数量少于 q q q的数量

思路 :

ll p,q;

ll calc(ll x){
	ll ans = 1;
	
	for(int i=2;i>p>>q;
	
	if(p%q) cout