一点一点前进...

0%

利用欧拉函数求与n互质的数的个数 | 欧拉项目 | 72题

发表于 分类于 ， Disqus：

题目本身是问，分母不超过一百万的最简真分数的集合中包含多少元素？

考虑分数 n/d, 其中n 和 d 是正整数。如果 n < d 并且最大公约数 HCF(n,d)=1, 它被称作一个最简真分数。
如果我们将d ≤ 8的最简真分数按照大小的升序列出来，我们得到：
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5 , 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
可知该集合中共有21个元素。
d ≤ 1,000,000的最简真分数集合中包含多少个元素？

如果写代码就是遍历d，然后针对每个d求1到d-1中有多少个数与d互质（互质才能是最简真分数），求和。

假设我们有一个函数能够得到互质数的个数，那么这个题目很容易解决，代码如下： 

1
2
3
4
5
6
7
8
long count = 0;
for (int d = 2; d <= 1000000; d++)
{
    long thisCount = Utils.GetCoprimeCount(d);
    count += thisCount;
}

return count;

现在关键问题是，给定一个数n，如何求出1到n-1中，有多少个数与之互质。
前几天刚在《什么是数学》这本书中看完欧拉函数，这就用上了。
欧拉函数描述了这个问题的解：
$$
\varphi(x)=x(1-1/p_1)(1-1/p_2)(1-1/p_3)(1-1/p_4)\cdots(1-1/p_n)
$$
其中$$p_1, p_2, \ldots, p_n$$为x的所有质因数
又$$
x={p_1}^{k_1} + {p_2}^{k_2} + \cdots + {p_n}^{k_n}
$$
所以，$$\varphi(x)=\prod_{i=1}^n (p_i-1)*{p_i}^{k_i-1}$$

开始写代码实现欧拉函数求互质数的个数： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int GetCoprimeCount(int n)
{
    int ret = 1;
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            n /= i;
            ret *= i - 1;
            while (n % i == 0)
            {
                n /= i;
                ret *= i;
            }
        }
    }
    if (n > 1)
    {
        ret *= n - 1;
    }

    return ret;
}

简单解释两点，
if (n % i == 0)里面的ret *= i - 1;相当于$$\prod_{i=1}^n (p_i-1){p_i}^{k_i-1}$$里面的$$(p_i-1)$$，while里面的ret \= i;相当于$$p_i$$，整个while循环就相当于$${p_i}^{k_i-1}$$
后面的if是判断，如果n > 1，那么剩余的n肯定是质数，ret *= n - 1;就相当于$$p_i-1$$，与之对应的$$k_i$$是1。

综合起来，就能在短短的几秒钟里面得到答案了。