Carmichael Function
(math/number-theory/carmichael.hpp)

• View this file on GitHub
• Last update: 2024-01-08 17:31:43+09:00
• Include: #include "math/number-theory/carmichael.hpp"

Description

Carmichael 関数 $\lambda(n)$ の値を求める．これは，$n$ と互いに素である $n$ 以下の自然数 $a$ 全てに対して$a^m \equiv 1 \mod n$ を満たすような最小の自然数 $m$ を与える．

Euler の定理より $m = \phi(n)$ は上の条件を満たすが，それが最小の $m$ であるとは限らない．最小の $m$ が $\lambda(n)$ である．

Operations

• long long carmichael(long long n)
  • $\lambda(n)$ を求める
  • 時間計算量: $O(\sqrt{n})$

Depends on

• Prime Number Algorithms (math/number-theory/prime.hpp)

Code

#pragma once
#include <cmath>
#include <numeric>

#include "prime.hpp"

long long carmichael(long long n) {
    long long ret = 1;
    for (auto [p, e] : prime_factor(n)) {
        long long lambda = std::pow(p, e - 1) * (p - 1);
        if (p == 2 && e >= 3) lambda /= 2;
        ret = ret / std::gcd(ret, lambda) * lambda;
    }
    return ret;
}

#line 2 "math/number-theory/carmichael.hpp"
#include <cmath>
#include <numeric>

#line 2 "math/number-theory/prime.hpp"
#include <map>
#line 4 "math/number-theory/prime.hpp"
#include <vector>

/*
 * Primality Test
 */
bool is_prime(long long n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    if (n < 9) return true;
    for (long long i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

/*
 * Prime Table
 */
std::vector<bool> prime_table(int n) {
    std::vector<bool> prime(n + 1, true);
    prime[0] = prime[1] = false;
    for (int j = 4; j <= n; j += 2) prime[j] = false;
    for (int i = 3; i * i <= n; i += 2) {
        if (!prime[i]) continue;
        for (int j = i * i; j <= n; j += 2 * i) prime[j] = false;
    }
    return prime;
}

/*
 * Table of Minimum Prime Factors
 */
std::vector<int> min_factor_table(int n) {
    std::vector<int> factor(n + 1);
    std::iota(factor.begin(), factor.end(), 0);
    for (int i = 2; i * i <= n; ++i) {
        if (factor[i] != i) continue;
        for (int j = i * i; j <= n; j += i) {
            if (factor[j] == j) factor[j] = i;
        }
    }
    return factor;
}

/*
 * Prime Factorization
 */
std::map<long long, int> prime_factor(long long n) {
    std::map<long long, int> ret;
    if (n % 2 == 0) {
        int cnt = 0;
        while (n % 2 == 0) {
            ++cnt;
            n /= 2;
        }
        ret[2] = cnt;
    }
    for (long long i = 3; i * i <= n; i += 2) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) {
                ++cnt;
                n /= i;
            }
            ret[i] = cnt;
        }
    }
    if (n != 1) ret[n] = 1;
    return ret;
}
#line 6 "math/number-theory/carmichael.hpp"

long long carmichael(long long n) {
    long long ret = 1;
    for (auto [p, e] : prime_factor(n)) {
        long long lambda = std::pow(p, e - 1) * (p - 1);
        if (p == 2 && e >= 3) lambda /= 2;
        ret = ret / std::gcd(ret, lambda) * lambda;
    }
    return ret;
}

Back to top page