HDU2588 – GCD

题目意思是 $[1,N]$ 区间内有多少个数 $X$ 使得 $GCD(X,N) ≥ M $。

首先不考虑数据范围的暴力思路是这样的:枚举$[1,N]$ 区间内若有的数 $X_i$,对于每一个 $X_i$,求 $GCD(X_i,N)$,如果满足$GCD(X_i,N) ≥ M $,则使用计数器累加。

显然对于这个庞大的数据是行不通的,我们需要换个角度思考。

假设 $$ GCD(X_i,N) = P \geq M $$


$$
N \mod P = 0 \\
GCD (\frac {X_i}{P} , \frac{N}{P}) = 1
$$
即P是N的因数,且原来的两个数除以他们的最大公因数P之后是互质的。

由于 $$ X_i \in [1,N] $$
所以 $$ X_i \leq N \Rightarrow \frac {X_i}{P} \leq \frac{N}{P}$$
那么我们只需要找到 $\frac {X_i}{P} ≤ \frac{N}{P}$ 的个数,其实就是比 $ \frac{N}{P} $ 小的且与其互质的数的个数,其实就是欧拉函数:
$$ \phi(\frac{N}{P}) $$

所以我们只需要枚举N的所有因数,得到一个 $\frac{N}{P}$,求到它的欧拉函数值,然后把所有的因数对应的 $\frac{N}{P}$ 的欧拉函数值相加,得到的和即是答案。

 

 

说点什么

avatar
50
  Subscribe  
提醒