欧拉函数

求单个欧拉函数

φ(n)表示1~n 中与n互质的数的个数。 $\psi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})···(1-\frac{1}{p_k})$ 其中：$n=p_1^{c1}p_2^{c2}···p_k^{ck}$

• 为避免浮点数除法，编程时采用另一个形式编写代码$\varphi \left( n \right) =n\left( \frac{p_1-1}{p_1} \right) \left( \frac{p_2-1}{p_2} \right) \cdots \left( \frac{p_k-1}{p_k} \right)$
• 可用先除后乘的方式res = res / n * (n-1)避免结果溢出
• 例子：$\varphi(6)=2$，因为$1$~$6$中只有$1$和$5$与$6$互质
• 可用容斥原理证明：$\varphi \left( n \right) =n-\sum_i{\frac{n}{p_i}+\sum_{i,j}{\frac{n}{p_i p_j}}-\sum_{i,j,k}{\frac{n}{p_i p_j p_k}}}+\cdots$
• 时间复杂度$O(\sqrt{n})$

代码

int phi(int x)
{
    int res = x;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    if (x > 1) res = res / x * (x - 1);

    return res;
}

筛法求多个欧拉函数

• 核心思想：$\varphi(n)$与$n$的质指数大小无关
  • 当$n$是质数时，$\varphi(n)=n-1$
  • 当$n \mod p = 0$时，$\varphi(pn)=p\varphi(n)$，因为质数$p$只影响$pn$的质指数$c_p$
  • 当$n \mod p \ne 0$时，$\varphi(pn)=p\varphi(n)(1-\frac{1}{p})=(p-1)\varphi(n)$，因为质数$p$影响了$pn$展开项数，多了一项$p^1$
• 借助线性筛法求欧拉函数，时间复杂度$O(n)$

代码

int primes[N], cnt;     // primes[]存储所有素数
int euler[N];           // 存储每个数的欧拉函数
bool st[N];         // st[x]存储x是否被筛掉（合数标记）


void get_eulers(int n)
{
    euler[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            // 质数
            primes[cnt ++ ] = i;
            euler[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0)
            {
                euler[t] = euler[i] * primes[j];
                break;
            }
            euler[t] = euler[i] * (primes[j] - 1);
        }
    }
}