欧拉函数

定义

image.png

证明

96d3ef6b38fbaae3b1b5d0636310ca3.jpg

应用

  • 题目:欧拉函数
  •   #include <iostream>
      #include <algorithm>
      using namespace std;
    
      using LL = long long;
    
      int main() {
          int t;
          cin >> t;
          while(t --) {
              int x;
              cin >> x;
              LL res = x;
    
              for (int i = 2; i <= x/i; ++ i) {
                  if (x % i == 0) {
                      res = res / i *(i - 1);
                      while (x % i == 0) {
                          x /= i;
                      }
                  }
              }
    
              if (x > 1)
                  res = res / x * (x - 1);
              cout << res << endl;
          }
          return 0;
      }
    

筛法求欧拉欧拉函数

这种写法是为了,应对题目要求 求 1~n中每个数的欧拉函数。可以在O(n) 的时间求出来。

情况讨论

  • 设 i 为当前赛选的数,pj 为质数, phi[i] 表示 i 的欧拉函数
    • 如果 i 是质数 phi[i] = i - 1;
    • 如果 i % pj == 0, 则 说明 pj,已经是 i 的质因数,又因为欧拉函数不受质因数的幂次影响。所以phi[i * pj] = pj * phi[i];
    • 如果 i % pj != 0, 则说明,pj是 i * pj, 新添加的质因数,所以 phi[i * pj] = pj * phi[i] * (1 - 1/pj) = phi[i] * (pj - 1);

应用

  • 题目:筛法求欧拉函数
  •   #include <iostream>
      #include <algorithm>
      using namespace std;
    
      const int N = 1e6 + 10;
    
      using ll = long long;
      ll primes[N], phi[N];
      ll cnt;
      bool st[N];
    
      ll olhs(int n) {
          for (int i = 2; i <= n; i ++) {
              if (!st[i]) {
                  st[i] = true;
                  primes[cnt++] = i;
                  phi[i] = i - 1;
              }
    
              for (int j = 0; primes[j] <= n/i; ++ j) {
                  st[primes[j] * i] = true;
                  if (i % primes[j] == 0) {
                      phi[i * primes[j]] = primes[j] * phi[i];
                      break;
                  }
                  phi[i * primes[j]] = phi[i] * (primes[j] - 1); 
              }
          }
    
          ll ans = 1; // 这里包含 1 的欧拉函数值 是 1
          for (int i = 1; i <= n; ++ i)
              ans += phi[i];
    
          return ans;
      }   
    
      int main() {
          int n;
          cin >> n;
    
          cout << olhs(n) << endl;
          return 0;
      }
    

欧拉定理

欧拉定理可以推出费马定理

具体证明看下面的图

09166e493d417d7091f528ce5ec76b5.jpg