歐拉函數及其性質與證明

歐拉函數:

歐拉函數是求1到n-1中與n互質的數，特殊的 φ(1)=1

歐拉通項(也就是公式):

其中pi是n的質因子。

證明:

由于在1到n中pi (也就是質因子) 的倍數是均勻分布的，那麼，去掉這些質因子的倍數(占1/pi)就是x * (1 - 1/pi)

那麼同理，其他質因子也按照這個來，就得到了上述公式

求單個歐拉值直接用唯一分解O(sqrt(n))就可以求得歐拉值

模闆

cin >> n;
        ll num = n;
        for(int i = 2;i * i <= n;i++)
        {
            if(n % i == 0)
            {
                num = num/i*(i-1);//先乘再除保證不會溢出
                while(n%i == 0)
                    n /= i;
            }
        }
        if(n > 1) num = num/n*(n-1);
        cout << num << endl;
           

當要求1到n的各個歐拉函數值的時候，可以利用埃氏篩和歐拉篩來降低時間複雜度

埃氏篩代碼

void euler(ll n)
{
    for(int i = 1;i <= n;i++) phi[i] = i;//因為每個歐拉值都要乘以自己，先預處理
    for(int i = 2;i <= n;i++)
    {
        if(!vis[i])//代表他是質數
        {
            for(int j = i;j <= n;j += i)//那麼他的倍數，一定擁有這個質因子
            {
                vis[j] = 1;
                phi[j] = phi[j]/i*(i-1);
            }
        }
    }
}
           

在介紹歐拉篩求歐拉函數時，先介紹一下性質:

1.歐拉函數是一個不完全積性函數，當n和m互質的時候，f(x * y) = f(x) * f(y)，不互質時不成立，是以叫不完全積性函數，那麼特殊的當n為奇數，那麼f(2*n) = f(n)，根據通項證明

2.當p為質數，且n = pk ， 那麼f(n) = pk - pk-1(證明:他是質數，那麼他的k次方隻能有p這一個質因子，那麼歐拉值為pk * (1 - 1/p) ，也就等于p k - p k-1)

3.對于質數f(n) = n-1(除了自己，其他的數都互質了)

4.當n > 2 是，歐拉值都是偶數 (那麼也說明了，與n互質的數都是成對出現的，且假設，小的那個數為m，那麼必有另外一個互質的數n-m)

5.小于n的互質的數，的和是f(n) * n/2，(根據第4條性質來，必然成對出現且成對的倆數和為n，那麼有f(n) / 2 對，每一對的和為n)

6.n的所有因子的歐拉值的和為n

7.當n % m == 0的時候，也就是n是m的倍數的時候，那麼m所擁有的所有質因子，n都有，根據通項公式知f(n * m) = f(n) * m

歐拉篩求歐拉函數

根據歐拉篩的特性，複雜度為O(n)

void euler(ll n)
{
    phi[1] = 1;
    for(ll i = 2;i <= n;i++)
    {
        if(!vis[i])
        {
            prime[m++] = i;
            phi[i] = i-1;//質數的歐拉值是i-1
        }
        for(ll j = 0;j < m && i * prime[j] <= n;j++)
        {
            vis[i*prime[j]] = 1;
            if(i % prime[j] == 0)
            {
                phi[i*prime[j]] = phi[i]*prime[j];//根據性質可得
                break;
            }
            else phi[i*prime[j]] = phi[i]*phi[prime[j]];//互質可積性
        }
    }
}