Aiur

zellux 的博客

Project Euler 351

Permalink

http://projecteuler.net/problem=351

整个六边形可以被切成 6 个三角形,每个三角形中被遮住的点数乘以 6 即为答案。对于每个三角形中的点,第 i 层第 j 个点能遮住第 m 层第 n 个点,当且仅当 $i < m$ 且 $\frac{i}{j} = \frac{n}{m}$。对于第 i 层第 j 个点,只有在 i j 互质时,这个点才能被看到,否则假设它们的最大公约数为 d,第 i / d 层第 j / d 个点能遮住它。

所以接下来的问题就是已经 n,求和 n 互质的正整数的个数。这个函数被称为欧拉商数(Euler’s totient function),求欧拉商数 $\varphi$ 的方法在 wikipedia 上有,有一个比较简单的计算公式:

$$ \varphi(n) = n \prod_{p|n}(1 - \frac{1}{p}) $$

(这里 p 是 n 的质因数)

用类似筛法求质数的方式,可以把所有范围内的整数的 $ \varphi $ 值计算出来,把它们相加即得到单个三角形中能看到的点的个数了,复杂度应该和筛法一样,为 $ O(n log{log{n}})) $.

评论