欧拉函数

欧拉函数

利用唯一分解定理,我们可以把一个整数唯一地分解为质数幂次的乘积。

欧拉定理

费马小定理

威尔逊定理

筛法求欧拉函数

void phi_table()
{
    for (int i = 1; i < maxn; i++) {
        phi[i] = i;
    }
    for (int i = 2; i < maxn; i++) {
        if (phi[i] == i) {
            for (int j = i; j < maxn; j += i) {
                phi[j] = phi[j] / i * (i - 1);
            }
        }
    }
}

Pollard Rho 算法求欧拉函数

ll get_phi(int n)
{
    ll res = 1;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            n /= i;
            res *= i - 1;
            while (n % i == 0) {
                n /= i;
                res *= i;
            }
        }
    }
    if (n > 1) {
        res *= n - 1;
    }
    return res;
}

最后更新于