Algorithm: Euler function

欧拉函数。

phi(n)表示比n小的与n互质的数的个数，比如

phi(1) = 1;

phi(2) = 1;

phi(3) = 2;

phi(4) = 2;

phi(5) = 4;

性质：

1. 如果p为质数，则phi(p) = p-1;

2. 如果p为质数并且a为正整数，则phi(p^a) = p^a - p^(a-1);

证明：p为质数，所以所有可以和p相乘小于p^a的数有p^a/p = p^(a-1)个，剩下的都与p^a互质。

3. phi(ab) = phi(a)*phi(b)

4. n = p1^a1*p2^a2*...*pk^ak

phi(n) = phi(p1^a1)*phi(p2^a2)*...*phi(pk^ak)

= (p1^a1-p1^(a1-1))*(p2^a2-p2^(a2-1))*...(pk^ak-pk^(ak-1))

=n*(1-1/p1)*(1-1/p2)*...*(1-1/pk)

实现代码：

 int phi (int n) {

     int result = n;

     for (int i=; i*i<=n; ++i)

         if (n % i == ) {

             while (n % i == )

                 n /= i;

             result -= result / i;

         }

     if (n > )

         result -= result / n;

     return result;

 }

应用：

欧拉定理：a^(phi(m)) = 1 (mod m)

其中a与m互质

费马定理：a^(m-1) = 1 (mod m)

其中a与m互质

巴特西

Algorithm: Euler function

最新文章

热门文章