数学知识之欧拉函数

对正整数n，欧拉函数是小于或等于n的数中与n互质的数的数目

$欧拉函数通常用\varphi (n) 表示$

若 $n = p^k$，则 $\varphi (n) = p^k - p^{k - 1}$

$\forall x \in Z _+ , 先分解成质因数相乘的格式$

$x = P_1^{c1} \times P_2^{c2} \times … \times P_n^{cn}$

$则有\varphi (x) = x \times (1 - \frac{1}{P1}) \times (1 - \frac{1}{P2}) \times … \times (1 - \frac{1}{Pn})$

$Code$

void init()//质数筛
{
    for (int i = 2; i < N; i ++ )
    {
        if (p[i])continue;
        q[++tot] = i;
        for (int j = 2; j <= N / i; j ++ )
            p[i * j] = true;
    }
}

int varphi(int n)
{
    init();

    int ans = n;
    for (int i = 1; i <= tot; i ++ )//分解质因数
    {
        int cnt = 0;
        while (n % q[i] == 0)
        {
            n /= q[i];
            cnt ++ ;
        }
        if (cnt)ans -= ans / q[i];
    }

    return ans;
}

$但是单个求复杂度太高,每个都需要O(n \log n)的复杂度,求1 \sim n的欧拉函数之和就要O(n^2 \log n)$

$这时就需要用到更快的$$线性筛法$$,并根据线性筛法的性质,顺带求出所有数的欧拉函数值$

$Code$

void init(int n)
{
    g[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!p[i])
        {
            q[++tot] = i;
            g[i] = i - 1;
        }
        for (int j = 1; q[j] <= n / i; j ++ )
        {
            p[i * q[j]] = true;
            if (i % q[j] == 0)
            {
                g[i * q[j]] = g[i] * q[j];
                break;
            }
            g[i * q[j]] = g[i] * (q[j] - 1);
        }
    }
}