HDU6287质因数分解、二分
题目
求解思路
给出$n$个数,每次询问区间$[l,r]$所有数的乘积是否是$X$的倍数。
$$a/b=0$$
$$a=p_1^{c_1}+p_2^{c_2}+p_3^{c_3}+… +p_n^{c_n}$$
$$b=p_1^{d_1}+p_2^{d_2}+p_3^{d_3}+… +p_n^{d_n}$$
则有
$$d_1<=c_1$$
$$d_2<=c_2$$
$$d_3<=c_3$$
$$…$$
$$d_n<=c_n$$
处理出所有质因子,并且将下标存入,这样要求质因子$x$在区间$[l,r]$出现的次数,只需二分即可。
代码
1 |
|