[Acwing] 200. Hankson的趣味题 预处理+质因数分解

前言

传送门 :

思路

给定 a 0 , a 1 , b 0 , b 1 a_0,a_1,b_0,b_1 a0​,a1​,b0​,b1​求有多少个 x x x满足

g c d ( x , a 0 ) = a 1 gcd(x,a_0)=a_1 gcd(x,a0​)=a1​ l c m ( x , b 0 ) = b 1 lcm(x,b_0)=b_1 lcm(x,b0​)=b1​

显然的,我们可以从 l c m ( x , b 0 ) = b 1 , x 是 b 1 的 约 数 lcm(x,b_0)=b_1,x是b_1的约数 lcm(x,b0​)=b1​,x是b1​的约数

因此我们可以暴力 所有 b 1 b_1 b1​的约数,然后对于每个约数都 c h e c k check check

时间复杂度 O ( T ∗ l o g n ∗ n ) O (T*logn*\sqrt{n}) O(T∗logn∗n ​) 大约是 8 ∗ 1 0 8 > 1 0 8 8*10^8>10^8 8∗108>108 因此是会被卡的

因此我们考虑优化

显然我们能优化的只是 n \sqrt{n} n ​

我们可以通过预处理 1 − N 1-N 1−N的所有质数,根据质数定理只有 N l n N \frac{\sqrt{N}}{ln\sqrt{N}} lnN ​N ​​ 个

然后通过枚举所有的质数,对 b 1 b1 b1进行质因数分解,最后通过 d f s dfs dfs将所有约数找出来

因此时间复杂度降到了 O ( T ∗ l o g n ∗ N l n N ) O(T*logn*\frac{\sqrt{N}}{ln\sqrt{N}}) O(T∗logn∗lnN ​N ​​)大约 4 ∗ 1 0 7 4*10^7 4∗107

Mycode

const int N = 4e4+5000, M = 50;
int primes[N] ,cnt;
bool st[N];

pii factor[N];
int cntf;


int divider[N],cntd;


//预处理出所有的质数
void get_primes(int n){
	for(int i=2;ia0>>a1>>b0>>b1;
	
	int d =  b1;//用于分解质因数
	cntf = 0 ;
	//b1 的所有约数
	for(int i=0;primes[i]1) factor[++cntf] = {d,1};
	
	cntd = 0 ;
	dfs(1,1);
	
	
	int res = 0 ;
	for(int i=0;i