Carmichael Totient - YessineJallouli/Competitive-Programming GitHub Wiki

Carmichael Totient Function

The Carmichael function (λ(n)), also known as the Carmichael totient function, is a function from number theory that provides important information about the modular arithmetic properties of integers.

Definition

For a given positive integer n, λ(n) is defined as the smallest positive integer m such that:

a^m ≡ 1 (mod n)

for all integers a that are coprime to n. In other words, λ(n) is the least common multiple of the orders of all integers modulo n that are coprime to n.

Implementation

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6+7;
int sieve[N], phi[N], carmichael[N];

void compute() {
    iota(phi, phi+N, 0);
    memset(sieve, -1, sizeof sieve);

    for (int i = 1; i < N; i++)
        for (int j = 2 * i; j < N; j += i)
            phi[j] -= phi[i];

    for (int i = 2; i < N; i++) {
        if (sieve[i] == -1) {
            for (int j = i; j < N; j += i) {
                if (sieve[j] == -1) {
                    int k = i;
                    while (j % (k * i) == 0) k *= i;
                    sieve[j] = k;
                }
            }
        }
    }

    for (int i = 1; i < N; i++) {
        if (i == 1 || i == 2 || i == 4 || (sieve[i] == i && i % 2))
            carmichael[i] = phi[i];
        else if ((i & (i - 1)) == 0)
            carmichael[i] = phi[i] / 2;
        else {
            int n = i, res = 1;
            while (n != 1) {
                int p = sieve[n];
                n /= p;
                res = lcm(res, carmichael[p]);
            }
            carmichael[i] = res;
        }
    }
}