? 最最開始的時候，我以為歐拉函數(shù)，歐拉定理，歐拉公式是一個東西，傻傻分不清。傻笑～

? 后來知道，這完完全全是三種東西！！要說有啥必然的聯(lián)系，它們可能都叫歐拉吧～

? 首先，我們來講一下三者的定義：

? 歐拉定理：若n,a為正整數(shù)且互質(zhì)，則a^(Φ(n)) = 1 (mod n)

? 歐拉公式：e^(i✖️x) = cos(x) + i✖️sin(x) （例如把x = π帶進(jìn)去，得e^(i✖️π) = -1）

? 歐拉函數(shù)：Φ(n)，用于求1～n中與n互質(zhì)的個數(shù)，若n為質(zhì)數(shù)，那么Φ(n) = n - 1
? 歐拉降冪：我們知道當(dāng)冪特別大的時候可以用快速冪來求，而當(dāng)冪大到10^1000時快速冪也求不了了。。這時候就需要用到歐拉降冪，它的定理如下（前提是a，p互質(zhì)）：

? a^b ≡ a^(b % Φ(p) + Φ(p)) (mod p)，當(dāng)x >= p時

? a^b ≡ a^(b % Φ(p)) (mod p)，當(dāng)x < p時

關(guān)于歐拉公式在ACM中我還沒有做過相關(guān)的題，因此先只講歐拉函數(shù)和歐拉降冪，歐拉定理

一.關(guān)于歐拉定理沒什么好說的～

? 之前我們說過一嘴費馬小定理：a ^ (p - 1 ) ≡ 1 (mod p)

? 又說過當(dāng)p為素數(shù)時Φ(p) = p - 1，因此歐拉定理實際上是費馬小定理的推廣

二.關(guān)于歐拉函數(shù)的求解，我們知道n為質(zhì)數(shù)的情況了，若n為合數(shù)呢？

? 學(xué)到了以下四種求法n的歐拉函數(shù)：

? 1.利用容斥原理：

? 我們先找到n的全部質(zhì)因子，然后利用容斥原理刪掉全部的因子，剩下的就是與n互質(zhì)的個數(shù)

? 例如30 = 2✖️3✖️5

? Φ(30) = 30 - 30 / 2 - 30 / 3 - 30 / 5 + 30 / (2✖️3) + 30 / (2✖️5) + 30 / (3✖️5) - 30 / (2✖️3✖️5)

? = 8

? 2.上面的寫法很麻煩，下面有種簡便的寫法：

? 30 = 30✖️1 / 2 ✖️2 / 3✖️4 / 5 = 8，這樣就能自動容斥啦，時間復(fù)雜度是O(sqrt(n))

? 3.埃篩法：

? 是不是很耳熟！！！對，求素數(shù)有埃篩和線篩，求歐拉函數(shù)也有埃篩和線篩～，埃篩的原理就是利用方法2～，時間復(fù)雜度是O(n✖️sqrt(n))

?

? 代碼如下：

void getEuler() {
    memset(euler, 0, sizeof(euler));
    euler[1] = 1;
    for (int i = 2; i <= N; i++) {
        if (!euler[i]) {
            for (int j = i; j <= N; j += i) {
                if (!euler[j]) {
                    euler[j] = j;					//若不存在先初始化
                }
                euler[j] = euler[j] / i * (i - 1);	//實質(zhì)就是方法2 
            }
        }
    }
}

?

? 4.線性篩

? 線性篩，顧名思義就是線性求解1～n的歐拉函數(shù)，需用到一下幾個性質(zhì)：

? 1.當(dāng)p為素數(shù)時，Φ(p) = p - 1;

? 2.當(dāng)p為素數(shù)且i % p ==0時，Φ(i✖️p) = Φ(i)✖️p

? 3.當(dāng)p為素數(shù)且i % p != 0時，Φ(i✖️p) = Φ(i)✖️(p - 1)

? 代碼如下：

ll phi[N + 5];	//存儲歐拉函數(shù)
ll prime[N + 5];	//存素數(shù)
void Euler() {
    phi[1] = 1;
<s 大專欄 (數(shù)論六)關(guān)于歐拉(定理、公式、函數(shù)、降冪)pan class="line">    memset(phi, 0, sizeof(phi));
 	prime[0] = 0;
    for (int i = 2; i <= N; i++) {
        if(!phi[i]) {				//若i為素數(shù)
            phi[i] = i - 1;
            prime[++prime[0]] = i;
        }
        for (int j = 1; j <= prime[0] && (ll)i * prime[j] <= N; j++) {
            if (i % prime[j]) {
                phi[i * prime[j]] = phi[i] * (prime[j] - 1);
            } else {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
        }
    }
    return;
}

三.歐拉降冪：

? 根據(jù) a^b ≡ a^(b % Φ(p) + Φ(p)) (mod p)，當(dāng)x >= p時

? a^b ≡ a^(b % Φ(p)) (mod p)，當(dāng)x < p時

? 我們可以得到以下代碼：

#define Mod(a, b) a < b? a: a % b + b   //重定義取模，按照歐拉定理的條件

map<ll,ll> mp;		//記憶化存儲歐拉函數(shù)

//按照歐拉定理的條件進(jìn)行快速冪
ll qpow(ll x, ll n, ll mod) {
    ll res = 1;
    while (n)
    {
        if (n & 1) {
            res = Mod(res * x, mod);
            n--;
        }
        x = Mod(x * x, mod);
        n >>= 1;
    }
    return res;
}

//求k的歐拉函數(shù)值
ll phi(ll k) {
    ll i;
    ll s = k;
    ll x = k;
    if (mp.count(k))
        return mp[x];                    //記憶化存儲
    for(i = 2; i * i <= k; i++) {
        if (k % i == 0)
            s = s / i * (i - 1);			//利用方法2
        while(k % i == 0)
            k /= i;
    }
    if(k > 1)
        s = s / k * (k - 1);
    mp[x]=s;
    return s;
}

注意！！當(dāng)快速冪需要用到之前的遞歸時，也需要迭代模!!!

? 例如 a[1]^(a[2]^(a[3]^(a[4]…)))

LL solve(LL l,LL r,LL mod) {
    if (l==r||mod==1) return Mod(a[l], mod);	//如果到右端點或者φ值等于1，那么直接返回當(dāng)前數(shù)字
    return qpow(a[l], solve(l+1, r, phi(mod)), mod);	//否則指數(shù)為[l+1,r]區(qū)間的結(jié)果
}

轉(zhuǎn)載請注明出處！！！

如果有寫的不對或者不全面的地方 可通過主頁的聯(lián)系方式進(jìn)行指正，謝謝

總結(jié)

以上是生活随笔為你收集整理的(数论六)关于欧拉(定理、公式、函数、降幂)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。