test/totient.test.cpp

• View this file on GitHub
• Last update: 2022-01-07 21:48:21+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_D

Depends on

• math/totient.cpp
• utility/int_alias.cpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_D"
#include "../utility/int_alias.cpp"
#include "../math/totient.cpp"
#include <iostream>

int main() {
    u32 x;
    std::cin >> x;
    std::cout << totient(x) << '\n';
    return 0;
}

#line 1 "test/totient.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_D"
#line 2 "utility/int_alias.cpp"
#include <cstdint>

using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
#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;
}
#line 4 "test/totient.test.cpp"
#include <iostream>

int main() {
    u32 x;
    std::cin >> x;
    std::cout << totient(x) << '\n';
    return 0;
}

Back to top page