math/totient_table.hpp

• View this file on GitHub
• Last update: 2023-02-06 17:52:27+09:00
• Include: #include "math/totient_table.hpp"

Verified with

• verify/aoj_other/aoj_2286.test.cpp

Code

#pragma once

std::vector<int> totient_table(int n) {
    std::vector<int> res(n + 1);
    std::iota(res.begin(), res.end(), 0);
    for (int p = 2; p <= n; p++) {
        if (res[p] != p) continue;
        for (int i = p; i <= n; i += p) {
            res[i] /= p;
            res[i] *= p - 1;
        }
    }
    return res;
}

#line 2 "math/totient_table.hpp"

std::vector<int> totient_table(int n) {
    std::vector<int> res(n + 1);
    std::iota(res.begin(), res.end(), 0);
    for (int p = 2; p <= n; p++) {
        if (res[p] != p) continue;
        for (int i = p; i <= n; i += p) {
            res[i] /= p;
            res[i] *= p - 1;
        }
    }
    return res;
}

Back to top page