Euler Function(オイラー関数)
(src/math/Euler-Function.hpp)

• View this file on GitHub
• Last update: 2022-08-12 22:24:53+09:00
• Include: #include "src/math/Euler-Function.hpp"

概要

long long euler_function(long long x)

引数 $x$ に対して $x$ 以下の正整数の中で $x$ と互いに素なものの個数を返します。

機能

64bit整数に収まる正整数をいれてください。

内部で zawa::factorize(x)を呼び出しています。

計算量

$O(\sqrt{x})$

Depends on

• Factorize(素因数分解) (src/math/factorize.hpp)

Verified with

• test/aoj_ntl_1_d.test.cpp

Code

#pragma once

#include "factorize.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 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

Back to top page