(数论六)关于欧拉(定理、公式、函数、降幂)

title

最最开始的时候，我以为欧拉函数，欧拉定理，欧拉公式是一个东西，傻傻分不清。傻笑～

后来知道，这完完全全是三种东西！！要说有啥必然的联系，它们可能都叫欧拉吧～

首先，我们来讲一下三者的定义：

欧拉定理：若n,a为正整数且互质，则a^(Φ(n)) = 1 (mod n)

欧拉公式：e^(i✖️x) = cos(x) + i✖️sin(x) （例如把x = π带进去，得e^(i✖️π) = -1）

欧拉函数：Φ(n)，用于求1～n中与n互质的个数，若n为质数，那么Φ(n) = n - 1
欧拉降幂：我们知道当幂特别大的时候可以用快速幂来求，而当幂大到10^1000时快速幂也求不了了。。这时候就需要用到欧拉降幂，它的定理如下（前提是a，p互质）：

a^b ≡ a^(b % Φ(p) + Φ(p)) (mod p)，当x >= p时

a^b ≡ a^(b % Φ(p)) (mod p)，当x < p时

关于欧拉公式在ACM中我还没有做过相关的题，因此先只讲欧拉函数和欧拉降幂，欧拉定理

一.关于欧拉定理没什么好说的～

之前我们说过一嘴费马小定理：a ^ (p - 1 ) ≡ 1 (mod p)

又说过当p为素数时Φ(p) = p - 1，因此欧拉定理实际上是费马小定理的推广

二.关于欧拉函数的求解，我们知道n为质数的情况了，若n为合数呢？

学到了以下四种求法n的欧拉函数：

1.利用容斥原理：

我们先找到n的全部质因子，然后利用容斥原理删掉全部的因子，剩下的就是与n互质的个数

例如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，这样就能自动容斥啦，时间复杂度是O(sqrt(n))

3.埃筛法：

是不是很耳熟！！！对，求素数有埃筛和线筛，求欧拉函数也有埃筛和线筛～，埃筛的原理就是利用方法2～，时间复杂度是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);	//实质就是方法2 
            }
        }
    }
}

4.线性筛

线性筛，顾名思义就是线性求解1～n的欧拉函数，需用到一下几个性质：

1.当p为素数时，Φ(p) = p - 1;

2.当p为素数且i % p ==0时，Φ(i✖️p) = Φ(i)✖️p

3.当p为素数且i % p != 0时，Φ(i✖️p) = Φ(i)✖️(p - 1)

代码如下：

ll phi[N + 5];	//存储欧拉函数
ll prime[N + 5];	//存素数
void Euler() {
    phi[1] = 1;
大专栏  (数论六)关于欧拉(定理、公式、函数、降幂)pan class="line">    memset(phi, 0, sizeof(phi));
 	prime[0] = 0;
    for (int i = 2; i <= N; i++) {
        if(!phi[i]) {				//若i为素数
            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;
}

三.欧拉降幂：

根据 a^b ≡ a^(b % Φ(p) + Φ(p)) (mod p)，当x >= p时

a^b ≡ a^(b % Φ(p)) (mod p)，当x < p时

我们可以得到以下代码：

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

map<ll,ll> mp;		//记忆化存储欧拉函数

//按照欧拉定理的条件进行快速幂
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的欧拉函数值
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;
}

注意！！当快速幂需要用到之前的递归时，也需要迭代模!!!

例如 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，那么直接返回当前数字
    return qpow(a[l], solve(l+1, r, phi(mod)), mod);	//否则指数为[l+1,r]区间的结果
}

转载请注明出处！！！

如果有写的不对或者不全面的地方可通过主页的联系方式进行指正，谢谢