src/math/number-theory/totient.hpp

View this file on GitHub
Last update: 2023-07-06 04:39:56+09:00
Include: #include "src/math/number-theory/totient.hpp"

Code

// count k \in [1, n]
//   s.t. k and n are relatively prime.
// O(sqrt(n))
template<typename T>
T totient(T n){
  T res = n;

  for (T i = 2; i * i <= n; i++) {
    if (n % i) continue;
    res = res / i * (i - 1);
    while (n % i == 0) n /= i;
  }

  if (n != 1) res = res / n * (n - 1);
  return res;
}

#line 1 "src/math/number-theory/totient.hpp"
// count k \in [1, n]
//   s.t. k and n are relatively prime.
// O(sqrt(n))
template<typename T>
T totient(T n){
  T res = n;

  for (T i = 2; i * i <= n; i++) {
    if (n % i) continue;
    res = res / i * (i - 1);
    while (n % i == 0) n /= i;
  }

  if (n != 1) res = res / n * (n - 1);
  return res;
}