数论-526互联

数论

欧拉函数

定义

欧拉函数 \(\phi(n)\) 表示 \([1,n]\) 之间与 \(n\) 互质的数量。

公式

设 \(n=\alpha_{1}^{p_1} \times \alpha_{2}^{p_2} \times \alpha_{3}^{p_3} \times …… \times \alpha_{k}^{p_k}\)

则 \(\phi(n) = n \times (1- \dfrac{1}{p_1})\times (1- \dfrac{1}{p_2})\times (1- \dfrac{1}{p_3}) \times …… \times (1- \dfrac{1}{p_k})\)

推导

如何推导

推导的方式要用到容斥原理。

欧拉函数 \(\phi(n)\) 代表的是 \([1,n]\) 之间与 \(n\) 互质的数量，但是我们发现比较难想，于是正难则反，直接从不互质来入手，然后减掉就得出结果了。

如果 \(i\) 与 \(n\) 不互质，那么 \(i\) 和 \(n\) 必将有共同的质因数。所以，我们可以通过 \(n\) 的每一个质因数进行倍数处理，然后容斥算出有多少是不互质的，因此也就可得出答案了。

推导过程

我们设：\(n\) 的质因数是：{ \(p_1,p_2,……,p_k\) }。

那么 \(p_i\) 在 \([1,n]\) 这个区间中的倍数就有 \(\dfrac{n}{p_i}\)。

为了方便推导，我们暂且先设 \(k=3\)。

于是就可以得到公式：

\(n-\dfrac{n}{p_1}-\dfrac{n}{p_2}-\dfrac{n}{p_3}+\dfrac{n}{p_1 \times p_2}+\dfrac{n}{p_1 \times p_3} + \dfrac{n}{p_2 \times p_3} -\dfrac{n}{p_1 \times p_2 \times p_3}\)

在进行通分之后，我们发现这个式子其实已经等于 \(\phi(n)\) 了。

性质

当 \(n\) 是质数的时候，\(\phi(n) = n-1\)。
当 \(n\) 是质数的时候，存在 \(n^k\) 使得 \(\phi(n^k) = (n-1) \times n ^{k-1}\)。
积性函数，如果 \(n\) 与 \(m\) 互质，则 \(\phi(n×m)=\phi(n)×\phi(m)\)。

代码

定义法

只能处理一个数的 \(\phi\)。

思路是一边分解质因数一遍处理欧拉函数

int get_euler(int n){
    int euler = n;
    for (int i = 2; i <= n / i; i++){
        if (n % i == 0){
            euler = euler / i * (i - 1) //euler = euler * (1 - 1 / i); 
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) euler = euler / n * (n - 1);
    return euler;
}

线性筛法

在进行筛法的时候处理欧拉函数

可以在一次线性筛中处理出 \([1,n]\) 中的欧拉函数

int primes[N], cnt = 0;
int euler[N];
bool st[N];

void get_euler(int n){
    euler[1] = 1; // 1的欧拉函数值是1
    // 线性筛模板 + 过程中求欧拉函数
    for (int i = 2; i <= n; i++){
        if (!st[i]){
            primes[cnt ++] = i;
            euler[i] = i - 1; // 性质1
        }
        for (int j = 0; primes[j] <= n / i; j++){
            st[i *primes[j]] = true;  
            if (i % primes[j] == 0){
                euler[i * primes[j]] = euler[i] * primes[j]; // 性质2
                break;
            }
            euler[i * primes[j]] = euler[i] * (primes[j] - 1); // 性质3
        }
    }
    // 最后，euler数组中存的就是 1 ~ n 每个数的欧拉函数值
    return ;
}