跳转至

欧拉函数

简述

欧拉函数的含义：表示的是小于等于 \(n\) 和 \(n\) 互质的数的个数。比如说 \(\varphi(1) = 1\)。

欧拉函数筛法计算（性质 8）：

\[ \varphi(x)=x*(1-1/p_1)(1-1/p_2)(1-1/p_3)(1-1/p_4)\cdots(1-1/p_n) \]

其中 \(p_1, p_2\cdots p_n\) 为 \(x\) 的所有质因数，\(x\) 是不为 0 的整数。

性质：
1. \(\varphi(1)=1\)
2. 对于素数 \(p\)，\(\varphi(p)=p-1\)
3. 小于 \(n\) 并与 \(n\) 互质的数的和为：\(n * \varphi(n) / 2\)
4. 欧拉定理：如果 \(a\) 与 \(n\) 互质，\(a^{\varphi(n)} \equiv 1 \pmod n\)
5. 积性：如果有 \(\gcd(a, b) = 1\)，那么 \(\varphi(a \times b) = \varphi(a) \times \varphi(b)\)。不是完全积性函数，\(a,b\) 不任取。特别地，当 \(n\) 是奇数时 \(\varphi(2n) = \varphi(2) \times \varphi(n) = \varphi(n)\)。
6. 反演：\(n = \sum_{d \mid n}{\varphi(d)}\)。
7. 若 \(n = p^k\)，其中 \(p\) 是质数，那么 \(\varphi(n) = p^k - p^{k - 1}\)。
8. 由唯一分解定理，设 \(n = \prod_{i=1}^{s}p_i^{k_i}\) （分解质因数），有：

\[ \varphi(n) = n \times \prod_{i = 1}^s{\dfrac{p_i - 1}{p_i}} \]
  1. 欧拉降幂（扩展欧拉定理）：\(A^{B} \equiv A^{B\bmod\varphi(C)+\varphi(C)}\pmod{C}\)

欧拉筛

每个数都只筛到其最小质因子倍（相当于取了个 min），那么每一个被筛掉的合数都是由最小的质因子筛掉。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
void init(int n) {
  for (int i = 2; i <= n; ++i) {
    if (!vis[i]) {
      pri[cnt++] = i;
    }
    for (int j = 0; j < cnt; ++j) {
      if (1ll * i * pri[j] > n) break;
      vis[i * pri[j]] = 1;
      if (i % pri[j] == 0) {
        // pri[j] 是 i 的最小质因子
        break;
      }
    }
  }
}

筛法 - OI Wiki

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void pre() {
  for (int i = 1; i <= 5000000; i++) {
    is_prime[i] = 1;
  }
  int cnt = 0;
  is_prime[1] = 0;
  phi[1] = 1;
  for (int i = 2; i <= 5000000; i++) {
    if (is_prime[i]) {
      prime[++cnt] = i;
      phi[i] = i - 1;
    }
    for (int j = 1; j <= cnt && i * prime[j] <= 5000000; j++) {
      is_prime[i * prime[j]] = 0;
      if (i % prime[j])
        phi[i * prime[j]] = phi[i] * phi[prime[j]];
      else {
        phi[i * prime[j]] = phi[i] * prime[j];
        break;
      }
    }
  }
}

优化：
只筛至平方根，is_prime只开到平方根
只筛奇数
用bitset

附录

参考/习题

LibreOJ

给定 \(n\)，计算下式的值：\(\sum_{i=1}^n\text{lcm}(i,n)\)

其中 \(\text{lcm}(i,n)\) 表示 \(i,n\) 的最小公倍数。

易得：

\[ \sum_{i=1}^{n} lcm(i,n)=n\sum_{i=1}^{n} \frac{i}{gcd(i,n)} \]

我们令 \(d=gcd(i,n)\) ，考虑每个 \(d\) 对答案的贡献（开始枚举 \(d\)）

\[ =n\sum_{i=1}^{n} \sum_{d} \frac{i}{d}[gcd(i,n)==d] \]

考虑到如果 \(gcd(i,n)==d\)，必然有 \(i\) 为 \(d\) 的倍数，因此不妨将 \(i\) 的意义替换为 \(i/d\)，也即：

\[ =n\sum_{d|n}\sum_{i=1}^{n/d} i[gcd(id,n)==d] \]
\[ =n\sum_{d|n}\sum_{i=1}^{n/d} i[gcd(i,n/d)==1] \]

有 \(n/d,d\) 两两配对可以互换：

\[ =n\sum_{d|n}\sum_{i=1}^{d} i[gcd(i,d)==1] \]

注意到\(\sum_{i=1}^{d} i[gcd(i,d)==1]\)表示\([1,d]\)中与\(d\)互质的数的和，它等于\(\frac{\varphi(d)d}{2}\)。

证明：

  • 当\(d>2\)时，\(\varphi(d)\)总是偶数，这是因为与\(d\)互质的数总是成对出现。具体来说，\(i\)与\(d\)互质，则\(d-i\)与\(d\)肯定也互质，它们的和是\(d\)，并且有\(\varphi(d)/2\)对。
  • 当\(d=2\)时，显然成立；当\(d=1\)时，定义其为\(1\)（要特判）。

于是上式化简为

\[ =n\sum_{d|n}\frac{\varphi(d)d}{2} \]

设

\[ f(d)=\sum_{d|n}\frac{\varphi(d)d}{2} \]

我们枚举 \(d\)，对于每个 \(2\le d\le maxn\)，把 \(\frac{\varphi(d)d}{2}\) 的贡献加到\(f(n)\)中去，最后加1，询问时再把最外面那个\(n\)乘进去。所以我们就可以在 \(O(n\log n)\) 的时间内预处理出所有的 \(f(n)\) ，每次查询 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using LL = long long;
using ull = unsigned long long;
using ld = long double;

const int maxn = 1e6, N = 1e6+10;

LL phi[N],f[N],prime[N];
bool is_prime[N];
void pre() {
  for (int i = 1; i <= maxn; i++) {
    is_prime[i] = 1;
  }
  int cnt = 0;
  is_prime[1] = 0;
  phi[1] = 1;
  for (int i = 2; i <= maxn; i++) {
    if (is_prime[i]) {
      prime[++cnt] = i;
      phi[i] = i - 1;
    }
    for (int j = 1; j <= cnt && i * prime[j] <= maxn; j++) {
      is_prime[i * prime[j]] = 0;
      if (i % prime[j])
        phi[i * prime[j]] = phi[i] * phi[prime[j]];
      else {
        phi[i * prime[j]] = phi[i] * prime[j];
        break;
      }
    }
  }
}

void calc(){
    for(int i=2;i<=maxn;i++){
        for(int j=i;j<=maxn;j+=i){
            f[j] += i*phi[i];
        }
        f[i] = f[i]/2 + 1;
    }
}

LL t,x;
int main() {
    std::ios::sync_with_stdio(0),cin.tie(0);
    pre(),calc();
    cin >> t;
    while(t--){
        cin >> x;
        cout << f[x]*x << '\n';
    }
    return 0;
}

小于正整数n且与n互质的正整数之和是多少？ - 知乎