数论-欧拉函数 学习笔记

一、欧拉函数

1.欧拉函数的定义

欧拉函数（Euler’s totient function），即 ，表示的是小于等于 和

比如说 。

当 n 是质数的时候，显然有 。

2.欧拉函数的一些性质

• 欧拉函数是积性函数。
  积性是什么意思呢？如果有，那么 。
  特别地，当 是奇数时 。
• 。
  利用​​莫比乌斯反演​​ 相关知识可以得出。
  也可以这样考虑：如果，那么 。
  如果我们设 表示 的数的个数，那么 。
  根据上面的证明，我们发现，，从而 。注意到约数 和 具有对称性，所以上式化为 。
• 若，其中 是质数，那么 。
  （根据定义可知）
• 由唯一分解定理，设，其中 是质数，有 。
  证明：

• 引理：设 为任意质数，那么 。
  证明：显然对于从 1 到 的所有数中，除了 个 的倍数以外其它数都与 互素，故 ，证毕。

接下来我们证明 。由唯一分解定理与

3.如何求欧拉函数值

如果只要求一个数的欧拉函数值，那么直接根据定义质因数分解的同时求就好了。这个过程可以用 ​​Pollard Rho​​ 算法优化。

int euler_phi(int n) {
    int m = int(sqrt(n + 0.5));
    int ans = n;
    for (int i = 2; i <= m; i++)
      if (n % i == 0) {
        ans = ans / i * (i - 1);
        while (n % i == 0) n /= i;
      }  
    if (n > 1) ans = ans / n * (n - 1);
    return ans;
}

注：如果将上面的程序改成如下形式，会提升一点效率：

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

二、欧拉定理、扩展欧拉定理 及其应用

1.欧拉定理

若 ，则 。

在实际的算法竞赛应用中，欧拉定理的应用更为频繁。

证明

构造一个与 ，再进行操作。

设 为模 意义下的一个简化剩余系，则 也为模 意义下的一个简化剩余系。所以 ，可约去 ，即得 。

当 为素数时，由于 ，代入欧拉定理可立即得到费马小定理。

2.扩展欧拉定理

当然也有扩展欧拉定理

证明略，有兴趣请参照： synapse7

3.欧拉降幂

由广义欧拉定理可知：

第2、3个公式表述的即为广义欧拉降幂，不要求与互质，但要求 与具有相应的大小关系。

我们不难发现，欧拉降幂的应用是十分模板化的，在这个降幂过程中的主要操作还是求欧拉函数的值。

​​例题：​​​求，其中

#include <bits/stdc++.h>
#define
#define
using namespace std;
char a[1000006];
ll x, z;
ll quickpow(ll x, ll y, ll z){
    ll ans = 1;
    while (y){
        if (y & 1) ans = ans * x % z;
        x = x * x % z;
        y >>= 1;
    }
    return ans;
}
ll phi(ll n){
    ll i, rea = n;
    for (i = 2; i * i <= n; i++){
        if (n % i == 0){
            rea = rea - rea / i;
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) rea = rea - rea / n;
    return rea;
}
int main(){
    while (scanf("%lld %s %lld", &x, a, &z) != EOF){
        ll len = strlen(a);
        ll p = phi(z);
        ll ans = 0;
        for (ll i = 0; i < len; i++) ans = (ans * 10 + a[i] - '0') % p;
        ans += p;
        printf("%lld\n", quickpow(x, ans, z));
    }
    return 0;
}

4.优化

可以使用线性筛优化。这部分内容单独开一篇博客。