Euler's totient function（オイラーのトーシェント関数）
(number/euler_totient_phi.hpp)

• View this file on GitHub
• Last update: 2021-05-05 10:47:28+09:00
• Include: #include "number/euler_totient_phi.hpp"
• Link: https://csacademy.com/contest/fii-code-2021-round-2/task/clown-fiesta/
• Link: https://kopricky.github.io/code/Computation_Advanced/tetration.html

Euler’s totient function $\varphi(n)$ は正の整数 $n$ に対して $n$ と互いに素な $n$ 以下の正の整数の個数．

使用例

std::vector<int> phi_table = euler_phi_table(N);  // N 以下の正の整数に対するテーブル作成 O(N log N)

auto phi = euler_phi<long long>(12345678910LL);  // 特定の整数に対する計算 O(sqrt N)

性質

• （オイラーの定理）$a$ と $n$ が互いに素なとき，$\displaystyle a^{\varphi(n)} \equiv 1 \pmod{n}$

問題例

• CS Academy FIICode 2021 Round #2 - Clown Fiesta

リンク

• Euler’s totient function - Wikipedia

Code

#pragma once
#include <numeric>
#include <vector>

// CUT begin
// Euler's totient function
// Complexity: O(NlgN)
std::vector<int> euler_phi_table(int N) {
    std::vector<int> ret(N + 1);
    std::iota(ret.begin(), ret.end(), 0);
    for (int p = 2; p <= N; p++) {
        if (ret[p] == p) {
            ret[p] = p - 1;
            for (int i = p * 2; i <= N; i += p) ret[i] = ret[i] / p * (p - 1);
        }
    }
    return ret;
}

// Euler's totient function
// Complexity: O(sqrtN)
// https://csacademy.com/contest/fii-code-2021-round-2/task/clown-fiesta/
// https://kopricky.github.io/code/Computation_Advanced/tetration.html
template <typename Int> Int euler_phi(Int n) {
    Int ret = n;
    if (n % 2 == 0) {
        ret /= 2;
        do { n /= 2; } while (n % 2 == 0);
    }
    if (n % 3 == 0) {
        ret = ret / 3 * 2;
        do { n /= 3; } while (n % 3 == 0);
    }
    for (Int i = 5; i * i <= n; i += 4) {
        if (n % i == 0) {
            ret = ret / i * (i - 1);
            do { n /= i; } while (n % i == 0);
        }
        i += 2;
        if (n % i == 0) {
            ret = ret / i * (i - 1);
            do { n /= i; } while (n % i == 0);
        }
    }
    if (n != 1) ret = ret / n * (n - 1);
    return ret;
}

#line 2 "number/euler_totient_phi.hpp"
#include <numeric>
#include <vector>

// CUT begin
// Euler's totient function
// Complexity: O(NlgN)
std::vector<int> euler_phi_table(int N) {
    std::vector<int> ret(N + 1);
    std::iota(ret.begin(), ret.end(), 0);
    for (int p = 2; p <= N; p++) {
        if (ret[p] == p) {
            ret[p] = p - 1;
            for (int i = p * 2; i <= N; i += p) ret[i] = ret[i] / p * (p - 1);
        }
    }
    return ret;
}

// Euler's totient function
// Complexity: O(sqrtN)
// https://csacademy.com/contest/fii-code-2021-round-2/task/clown-fiesta/
// https://kopricky.github.io/code/Computation_Advanced/tetration.html
template <typename Int> Int euler_phi(Int n) {
    Int ret = n;
    if (n % 2 == 0) {
        ret /= 2;
        do { n /= 2; } while (n % 2 == 0);
    }
    if (n % 3 == 0) {
        ret = ret / 3 * 2;
        do { n /= 3; } while (n % 3 == 0);
    }
    for (Int i = 5; i * i <= n; i += 4) {
        if (n % i == 0) {
            ret = ret / i * (i - 1);
            do { n /= i; } while (n % i == 0);
        }
        i += 2;
        if (n % i == 0) {
            ret = ret / i * (i - 1);
            do { n /= i; } while (n % i == 0);
        }
    }
    if (n != 1) ret = ret / n * (n - 1);
    return ret;
}

Back to top page