math/totient.cpp

• View this file on GitHub
• Last update: 2022-01-07 21:48:21+09:00

Required by

• algorithm/convolution_arbitrary_mod.cpp
• algorithm/convolution_int.cpp
• algorithm/convolution_mod.cpp
• math/static_modint.cpp

Verified with

• test/and_convolution.test.cpp
• test/berlekamp_massey.test.cpp
• test/convolution_arbitrary_mod.test.cpp
• test/convolution_mod.test.cpp
• test/fp_util.test.cpp
• test/heavy_light_decomposition.test.cpp
• test/lazy_segment_tree.test.cpp
• test/queue_aggregation.test.cpp
• test/segment_tree.test.cpp
• test/semiring_matrix.test.cpp
• test/subset_convolution.test.cpp
• test/totient.test.cpp

Code

#pragma once

template <class T> constexpr T totient(T x) {
    T ret = x;
    for (T i = 2; i * i <= x; ++i) {
        if (x % i == 0) {
            ret /= i;
            ret *= i - 1;
            while (x % i == 0) x /= i;
        }
    }
    if (x > 1) {
        ret /= x;
        ret *= x - 1;
    }
    return ret;
}

#line 2 "math/totient.cpp"

template <class T> constexpr T totient(T x) {
    T ret = x;
    for (T i = 2; i * i <= x; ++i) {
        if (x % i == 0) {
            ret /= i;
            ret *= i - 1;
            while (x % i == 0) x /= i;
        }
    }
    if (x > 1) {
        ret /= x;
        ret *= x - 1;
    }
    return ret;
}

Back to top page