カーマイケル関数 (Carmichael function) の数表
(include/emthrm/math/carmichael_function_init.hpp)

• View this file on GitHub
• Last update: 2023-02-25 16:35:06+09:00
• Include: #include "emthrm/math/carmichael_function_init.hpp"

カーマイケル関数 (Carmichael function)

$n \in \mathbb{N}^+$ に対して

\[\forall a \in \mathbb{N}^+,\ a \perp n \implies a^x \equiv 1 \pmod{n}\]

を満たす最小の $x \in \mathbb{N}^+$ を $\lambda(n)$ と定義する。

素因数分解 $n = \prod_{i = 1}^k p_i^{e_i}$ に対して

\[\lambda(n) = \begin{cases} 1 & (n = 1, 2), \\ 2 & (n = 4), \\ 2^{e - 2} & (\exists e \geq 3,\ n = 2^e), \\ (p - 1)p^{e - 1} & (\exists p \text{ : 奇素数},\ \exists e \in \mathbb{N}^+,\ n = p^e), \\ \mathrm{lcm} (\lambda(p_1^{e_1}),\ldots, \lambda(p_k^{e_k})) & (\text{otherwise}) \end{cases}\]

が成り立つ。

仕様

名前	戻り値
long long carmichael_function(long long n);	カーマイケル関数 $\lambda(n)$

数表

名前	戻り値
std::vector<long long> carmichael_function_init(const long long low, const long long high);	カーマイケル関数 $\lambda(n)$ ($\mathrm{low} \leq n \leq \mathrm{high}$) の数表

参考文献

• Robert D. Carmichael: Note on a new number theory function, Bulletin of the American Mathematical Society, Vol. 16, pp. 232–238 (1910). https://doi.org/10.1090/S0002-9904-1910-01892-9
• http://integers.hatenablog.com/entry/2017/06/08/191649
• https://en.wikipedia.org/wiki/Carmichael_function
• https://github.com/spaghetti-source/algorithm/blob/8af3698b8a7583035857280ab324c8ae75c70374/number_theory/carmichael_lambda.cc

TODO

• https://onlinejudge.u-aizu.ac.jp/problems/2720

Depends on

• prime sieve (include/emthrm/math/prime_sieve.hpp)

Code

#ifndef EMTHRM_MATH_CARMICHAEL_FUNCTION_INIT_HPP_
#define EMTHRM_MATH_CARMICHAEL_FUNCTION_INIT_HPP_

#include <numeric>
#include <vector>

#include "emthrm/math/prime_sieve.hpp"

namespace emthrm {

std::vector<long long> carmichael_function_init(const long long low,
                                                const long long high) {
  std::vector<long long> lambda(high - low, 1), tmp(high - low);
  std::iota(tmp.begin(), tmp.end(), low);
  if (low == 0 && high > 0) lambda[0] = 0;
  for (long long i = (low + 7) / 8 * 8; i < high; i += 8) {
    tmp[i - low] >>= 1;
  }
  long long root = 1;
  while ((root + 1) * (root + 1) < high) ++root;
  for (const int p : prime_sieve<true>(root)) {
    for (long long i = (low + p - 1) / p * p; i < high; i += p) {
      if (i == 0) continue;
      tmp[i - low] /= p;
      long long phi = p - 1;
      for (; tmp[i - low] % p == 0; tmp[i - low] /= p) {
        phi *= p;
      }
      lambda[i - low] = std::lcm(lambda[i - low], phi);
    }
  }
  for (int i = 0; i < high - low; ++i) {
    if (tmp[i] > 1) lambda[i] = std::lcm(lambda[i], tmp[i] - 1);
  }
  return lambda;
}

}  // namespace emthrm

#endif  // EMTHRM_MATH_CARMICHAEL_FUNCTION_INIT_HPP_

#line 1 "include/emthrm/math/carmichael_function_init.hpp"



#include <numeric>
#include <vector>

#line 1 "include/emthrm/math/prime_sieve.hpp"



#line 6 "include/emthrm/math/prime_sieve.hpp"

namespace emthrm {

template <bool GETS_ONLY_PRIME>
std::vector<int> prime_sieve(const int n) {
  std::vector<int> smallest_prime_factor(n + 1), prime;
  std::iota(smallest_prime_factor.begin(), smallest_prime_factor.end(), 0);
  for (int i = 2; i <= n; ++i) {
    if (smallest_prime_factor[i] == i) [[unlikely]] prime.emplace_back(i);
    for (const int p : prime) {
      if (i * p > n || p > smallest_prime_factor[i]) break;
      smallest_prime_factor[i * p] = p;
    }
  }
  return GETS_ONLY_PRIME ? prime : smallest_prime_factor;
}

}  // namespace emthrm


#line 8 "include/emthrm/math/carmichael_function_init.hpp"

namespace emthrm {

std::vector<long long> carmichael_function_init(const long long low,
                                                const long long high) {
  std::vector<long long> lambda(high - low, 1), tmp(high - low);
  std::iota(tmp.begin(), tmp.end(), low);
  if (low == 0 && high > 0) lambda[0] = 0;
  for (long long i = (low + 7) / 8 * 8; i < high; i += 8) {
    tmp[i - low] >>= 1;
  }
  long long root = 1;
  while ((root + 1) * (root + 1) < high) ++root;
  for (const int p : prime_sieve<true>(root)) {
    for (long long i = (low + p - 1) / p * p; i < high; i += p) {
      if (i == 0) continue;
      tmp[i - low] /= p;
      long long phi = p - 1;
      for (; tmp[i - low] % p == 0; tmp[i - low] /= p) {
        phi *= p;
      }
      lambda[i - low] = std::lcm(lambda[i - low], phi);
    }
  }
  for (int i = 0; i < high - low; ++i) {
    if (tmp[i] > 1) lambda[i] = std::lcm(lambda[i], tmp[i] - 1);
  }
  return lambda;
}

}  // namespace emthrm

Back to top page