Hexo
0%

欧拉函数

Posted on In ,
Symbols count in article: 279 Reading time ≈ 1 mins.

欧拉函数

求小于等于n和n互质的数的个数

$\alpha(n)$

1
2
3
4
5
6
7
8
9
10
11
12
#include <cmath>

int euler_phi(int n) {
  int ans = n;
  for (int i = 2; i * i <= n; i++)
    if (n % i == 0) {
      ans = ans / i * (i - 1);
      while (n % i == 0) n /= i;
    }
  if (n > 1) ans = ans / n * (n - 1);
  return ans;
}

欧拉定理

$若\ gcd(a,m)\ =\ 1,则a^{\alpha(m) }\ \equiv \ 1\ (mod\ m)$