img

欧拉函数

一直没研究太懂，我想这下就很好懂了

欧拉函数定义

在数论中，对正整数n，欧拉函数φ(n)是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为φ函数（由高斯所命名）或是欧拉总计函数（totient function，由西尔维斯特所命名）。

例如φ(8) = 4，因为1,3,5,7均和8互质。

标准分解式

标准分解式：将质因数分解的结果，按照质因数大小，由小到大排列，并将相同质因数的连乘积，以指数形式表示，此种表示法称为标准分解式。

image-20240314083205819

第一个性质中，在不大于\(p^n\)的正整数中，不与之互质的只有p的整数，p,2p,3p........一共有\(p^n-1\)个，因此得证第一个式子

第二个性质的话显然合理

第三个性质则是欧拉函数属于积性函数的性质。

则经过推理最后

我们得到了公式

先将正整数进行质因数分解

image-20240314083558264

然后由于两两互质和欧拉函数的积性函数的性质

因此既可以将这个公式变化为：

image-20240314083640813

最后就可以得到

image-20240314083654980

最后就可以得到整个欧拉函数了

这里给出欧拉函数以\(\sqrt{n}\)的的复杂度求解正整数的欧拉函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int phi(int n)
{
    int res = n;
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
            res = res / i * (i - 1); // 先除再乘防止溢出
        while (n % i == 0) // 每个质因数只处理一次，可以把已经找到的质因数除干净
            n /= i;
    }
    if (n > 1)
        res = res / n * (n - 1); // 最后剩下的部分也是原来的n的质因数
    return res;
}

欧拉函数也可以与筛法进行结合，比如利用埃式筛就可以顺便求解出1-n的欧拉函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void init(int n)
{
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!isnp[i])
            primes.push_back(i), phi[i] = i - 1; 
        // 性质一，素数指数为1的情形
        for (int p : primes)
        {
            if (p * i > n)
                break;
            isnp[p * i] = 1;
            if (i % p == 0)
            {
                phi[p * i] = phi[i] * p; 
                // 性质二，整除直接求解倍数
                break;
            }
            else
                phi[p * i] = phi[p] * phi[i]; 
            // 这时肯定互质，用性质三
        }
    }
}