src/jiangly/math/06A-Phi.hpp

• View this file on GitHub
• Last update: 2025-02-17 23:08:47+08:00
• Include: #include "src/jiangly/math/06A-Phi.hpp"
• Link: https://atcoder.jp/contests/tenka1-2017/submissions/46411797

Code

/**   欧拉函数（求解单个数的欧拉函数）
 *    2023-10-09: https://atcoder.jp/contests/tenka1-2017/submissions/46411797
**/
int phi(int n) {
    int res = n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0) {
                n /= i;
            }
            res = res / i * (i - 1);
        }
    }
    if (n > 1) {
        res = res / n * (n - 1);
    }
    return res;
}

#line 1 "src/jiangly/math/06A-Phi.hpp"
/**   欧拉函数（求解单个数的欧拉函数）
 *    2023-10-09: https://atcoder.jp/contests/tenka1-2017/submissions/46411797
**/
int phi(int n) {
    int res = n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0) {
                n /= i;
            }
            res = res / i * (i - 1);
        }
    }
    if (n > 1) {
        res = res / n * (n - 1);
    }
    return res;
}

Back to top page