test/aoj_ntl_1_d.test.cpp

View this file on GitHub
Last update: 2022-08-12 22:25:13+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_D

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_D"

#include <iostream>
#include "../src/math/Euler-Function.hpp"

int main() {
    long long n;
    std::cin >> n;
    std::cout << zawa::euler_function(n) << std::endl;
}

#line 1 "test/aoj_ntl_1_d.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_D"

#include <iostream>
#line 2 "src/math/Euler-Function.hpp"

#line 2 "src/math/factorize.hpp"

#include <vector>

namespace zawa {

    std::vector<std::pair<long long, int>> factorize(long long x) {
        std::vector<std::pair<long long, int>> res;

        for (long long i = 2 ; i * i <= x ; i++) {
            if (x % i) continue;
            int cnt = 0;
            while (!(x % i)) {
                cnt++;
                x /= i;
            }
            res.emplace_back(i, cnt);
        }
        if (x != 1) res.emplace_back(x, 1);

        return res;
    }

} // namespace zawa
#line 4 "src/math/Euler-Function.hpp"

namespace zawa {
    
    long long euler_function(long long x) {
        long long res = x;

        for (auto v : zawa::factorize(x)) {
            res /= v.first;
            res *= v.first - 1;
        }

        return res;
    }

}// namespace zawa
#line 5 "test/aoj_ntl_1_d.test.cpp"

int main() {
    long long n;
    std::cin >> n;
    std::cout << zawa::euler_function(n) << std::endl;
}