跳转至

欧拉函数

定义

\(\phi(n)=\sum^n_{i=1}[\gcd(i,n)==1]\)

定理

① 若 \(\gcd(p,q)=1\) 则 \(\phi(p\cdot{q})=\phi(p)\cdot\phi(q)\)

② \(n\) 为正整数 有 \(n=\sum_{d|n}\phi(d)\)

③ \(n=p_1^{a_1}\cdot p_2^{a_2}\cdot…\cdot p_s^{a_s}\) 是正整数 \(n\) 的质幂因子分解 则

\[ \begin{align} \phi(n)&=n\cdot(1-\frac{1}{p_1})\cdot(1-\frac{1}{p_2})\cdot…\cdot(1-\frac{1}{p_s})\\ &=n\cdot\prod_{i=1}^s(1-\frac{1}{p_i}) \end{align} \]

求欧拉函数

模版
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
i64 euler_phi(i64 n) {
    i64 ans = n;
    for (int i = 2 ; 1LL * 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;
}
C++
 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
namespace EulerSieve {
    vector<int> prime, phi;
    vector<bool> vis;
    void _EulerSieveInit(int n) {
        n++;
        vis.resize(n);
        vis[1] = true;
        phi.resize(n);
        phi[1] = 1;
        for (int i = 2 ; i < n ; i++) {
            if (!vis[i]) {
                prime.emplace_back(i);
                phi[i] = i - 1;
            }
            for (auto &x : prime) {
                if (1LL * i * x >= n) break;
                vis[i * x] = true;
                if (i % x == 0) {
                    phi[i * x] = phi[i] * x;
                    break;
                }
                phi[i * x] = phi[i] * phi[x];
            }
        }
    }
    void primeInit(int n) {
        _EulerSieveInit(n);
    }
} // EulerSieve
using namespace EulerSieve;

扩展欧拉定理

\[ a^b\equiv\begin{cases} a^{b\mod\phi(p)}&\gcd(a,p)=1\\ a^b&\gcd(a,p)\neq1,b<\phi(p)\\ a^{b\mod\phi(p)+\phi(p)}&\gcd(a,p)\neq1,b\geq\phi(p) \end{cases}\pmod{p} \]
例题

P5091 【模板】扩展欧拉定理 - 洛谷

代码
C++
 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
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
i64 euler_phi(i64 n) {
    i64 ans = n;
    for (int i = 2 ; 1LL * 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;
}
i64 qpow(i64 a, i64 b, i64 P, i64 res = 1) {
    while (b) {
        if (b & 1) res = res * a % P;
        a = a * a % P;
        b >>= 1;
    }
    return res;
}
int main() {
    int a, m;
    cin >> a >> m;
    string b;
    cin >> b;
    i64 k = euler_phi(m);
    bool flag = false;
    i64 res = 0;
    for (int i = 0 ; i < (int) b.size() ; i++) {
        res = res * 10 + (b[i] ^ 48);
        if (res > k) {
            res %= k;
            flag = true;
        }
    }
    if (flag) res += k;
    cout << qpow(a, res, m);
    return 0;
}
习题

P4139 上帝与集合的正确用法 - 洛谷

已知 \(a_0=1,a_n=2^{a_{n-1}}\)，问 \(a_n\mod p\) 的值

Code
C++
 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
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
namespace EulerSieve {
    vector<int> prime, phi;
    vector<bool> vis;
    void _EulerSieveInit(int n) {
        n++;
        vis.resize(n);
        vis[1] = true;
        phi.resize(n);
        phi[1] = 1;
        for (int i = 2 ; i < n ; i++) {
            if (!vis[i]) {
                prime.emplace_back(i);
                phi[i] = i - 1;
            }
            for (auto &x : prime) {
                if (1LL * i * x >= n) break;
                vis[i * x] = true;
                if (i % x == 0) {
                    phi[i * x] = phi[i] * x;
                    break;
                }
                phi[i * x] = phi[i] * phi[x];
            }
        }
    }
    void primeInit(int n) {
        _EulerSieveInit(n);
    }
} // EulerSieve
using EulerSieve::phi;
i64 qpow(i64 a, i64 b, i64 P, i64 res = 1) {
    while (b) {
        if (b & 1) {
            res = res * a % P;
        }
        a = a * a % P;
        b >>= 1;
    }
    return res;
}
i64 get(i64 P) {
    if (P == 1) return 0;
    return qpow(2, get(phi[P]) + phi[P], P);
}
void solve() {
    int p;
    cin >> p;
    cout << get(p) << "\n";
}
int main() {
    EulerSieve::primeInit(10000000);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

P3747 [六省联考 2017] 相逢是问候 - 洛谷

操作一: 区间 \([L,R]\) 的 \(a_i=c^{a_i}\)

操作二: 查询区间 \([L,R]\) 的和 模 \(p\)

代码
C++
  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
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
const int N = 50005;
i64 a[N][60];
vector<array<i64, 2>> lsp[60];
vector<int> phi, B;
int c, P;
i64 euler_phi(i64 n) {
    i64 ans = n;
    for (int i = 2 ; 1LL * 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;
}
i64 qpow(i64 b, int idx) {
    i64 k = lsp[idx][b % B[idx]][0] * lsp[idx][b / B[idx]][1];
    if (k >= phi[idx]) {
        k = k % phi[idx] + phi[idx];
    }
    return k;
}
i64 get(i64 x, int cnt, int idx) {
    if (cnt == 0) {
        if (x >= phi[idx]) {
            x = x % phi[idx] + phi[idx];
        }
        return x;
    }
    if (phi[idx] == 1) {
        return c ? 1 : 0;
    }
    return qpow(get(x, cnt - 1, idx + 1), idx);
}
struct Node {
    int L, R, cnt;
    i64 sum;
} tr[N << 2];
Node merge(Node &x, Node &y) {
    return {x.L, y.R, min(x.cnt, y.cnt), (x.sum + y.sum) % P};
}
void pushup(int p) {
    tr[p] = merge(tr[p << 1], tr[p << 1 | 1]);
}
void build(int p, int L, int R) {
    if (L == R) {
        tr[p] = {L, R, 0, a[L][0]};
        return;
    }
    int mid = L + R >> 1;
    build(p << 1, L, mid);
    build(p << 1 | 1, mid + 1, R);
    pushup(p);
}
void modify(int p, int QL, int QR) {
    if (tr[p].cnt >= phi.size()) {
        return;
    }
    if (tr[p].L == tr[p].R) {
        tr[p].cnt++;
        tr[p].sum = a[tr[p].L][tr[p].cnt];
        return;
    }
    int mid = tr[p].L + tr[p].R >> 1;
    if (QL <= mid) modify(p << 1, QL, QR);
    if (QR >= mid + 1) modify(p << 1 | 1, QL, QR);
    pushup(p);
}
i64 query(int p, int QL, int QR) {
    if (QL <= tr[p].L && tr[p].R <= QR) {
        return tr[p].sum % P;
    }
    i64 res = 0;
    int mid = tr[p].L + tr[p].R >> 1;
    if (QL <= mid) {
        res = (res + query(p << 1, QL, QR)) % P;
    }
    if (QR >= mid + 1) {
        res = (res + query(p << 1 | 1, QL, QR)) % P;
    }
    return res;
}
int main() {
    int n, m;
    cin >> n >> m >> P >> c;
    int tP = P;
    while (tP != 1) {
        B.push_back(10000);
        int idx = phi.size();
        lsp[idx].resize(B[idx] + 1);
        lsp[idx][0] = {1, 1};
        for (int i = 1 ; i <= B[idx] ; i++) {
            lsp[idx][i][0] = lsp[idx][i - 1][0] * c;
            if (lsp[idx][i][0] >= tP) {
                lsp[idx][i][0] = lsp[idx][i][0] % tP + tP;
            }
        }
        for (int i = 1 ; i <= B[idx] ; i++) {
            lsp[idx][i][1] = lsp[idx][i - 1][1] * lsp[idx][B[idx]][0];
            if (lsp[idx][i][1] >= tP) {
                lsp[idx][i][1] = lsp[idx][i][1] % tP + tP;
            }
        }
        phi.push_back(tP);
        tP = euler_phi(tP);
    }
    phi.push_back(1);
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i][0];
        for (int j = 1 ; j <= (int) phi.size() ; j++) {
            a[i][j] = get(a[i][0], j, 0) % P;
        }
        a[i][0] %= P;
    }
    build(1, 1, n);
    while (m--) {
        int op, L, R;
        cin >> op >> L >> R;
        if (op == 0) {
            modify(1, L, R);
        } else {
            cout << query(1, L, R) << "\n";
        }
    }
    return 0;
}