定理及其扩展"/>

浅谈欧拉定理及其扩展

欧拉定理

​ 欧拉定理其实是费马小定理的一个推广，首先来回顾一下费马小定理。

费马小定理

​ p为质数，且a不是p的倍数，则有
a p − 1 ≡ 1 ( m o d p ) a^{p-1} \equiv 1 \quad (mod \quad p) ap−1≡1(modp)

欧拉定理

​ 设p是任意大于1的整数，且(a, m)=1，则有
a φ ( p ) ≡ 1 ( m o d p ) a^{\varphi(p)}\equiv 1 \quad (mod \quad p) aφ(p)≡1(modp)
​ φ \varphi φ§指的是从1到p-1中，与p互素的元素的个数。

​ 举个例子来深度理解一下欧拉定理，假如p = 20， a = 3，可知a与p互素，则有

a 0 ≡ 1 a 1 ≡ 3 a 2 ≡ 9 a 3 ≡ 7 a 4 ≡ 1 a^{0} \equiv 1 \\a^{1} \equiv 3 \\a^{2} \equiv 9 \\a^{3} \equiv 7 \\a^{4} \equiv 1 a0≡1a1≡3a2≡9a3≡7a4≡1
不难发现当取到 a 4 a^{4} a4时再次出现了1的情况，因此以后都是以4为一个循环，那再假如p = 20，a = 2，则有
a 0 ≡ 1 a 1 ≡ 2 a 2 ≡ 4 a 3 ≡ 8 a 4 ≡ 16 a 5 ≡ 12 a 6 ≡ 4 a^{0} \equiv 1 \\a^{1} \equiv 2 \\a^{2} \equiv 4 \\a^{3} \equiv 8 \\a^{4} \equiv 16 \\a^{5} \equiv 12 \\a^{6} \equiv 4 a0≡1a1≡2a2≡4a3≡8a4≡16a5≡12a6≡4
此时，发现 a 2 ≡ a 6 a^{2} \equiv a^{6} a2≡a6显然，循环不是从第一个元素开始，是先经过一段不循环的数，然后再进入到循环当中。

综上，可以得出结论，当 ( a , p ) = 1 (a, p)=1 (a,p)=1时，从一开始就进入了循环当中，当 ( a , p ) ≠ 1 (a, p)\neq 1 (a,p)=1时，是先经过一段不循环的数，然后再进入到循环当中。

扩展欧拉定理

扩展欧拉定理一般用来欧拉降幂

先给出公式：
a m ≡ { a m , if  m < φ ( p ) a m % φ ( p ) + φ ( p ) , if  m ≥ φ ( p ) a^{m} \equiv \begin{cases} a^{m},& \text{if $m < \varphi(p)$}\\ a^{m \% \varphi(p) + \varphi(p)},& \text{if $m \geq \varphi(p)$} \end{cases} am≡{am,am%φ(p)+φ(p),​if m<φ(p)if m≥φ(p)​
当 m < φ ( p ) m<\varphi(p) m<φ(p)时，说明m只在第一个循环或者甚至不在循环当中，直接快速幂求解即可。

当 m ≥ φ ( p ) m \geq \varphi(p) m≥φ(p)时，说明m已经在循环当中，需要确定的就是他在循环当中的哪个数，a的幂次是 m % φ ( p ) + φ ( p ) m\% \varphi(p)+\varphi(p) m%φ(p)+φ(p)实际上是化简后的 ( m − φ ( p ) ) % φ ( p ) + φ ( p ) (m-\varphi(p))\%\varphi(p)+\varphi(p) (m−φ(p))%φ(p)+φ(p)，加上一个 φ ( p ) \varphi(p) φ(p)就是为了让其先进入循环中，然后再去确定他在循环当中的哪个数。

模板题

Notepad

题意易懂，因为没有前导0，所以第一位只有(b-1)种情况，所以答案其实就是 a n s ≡ ( b − 1 ) ∗ b n − 1 m o d c ans\equiv (b-1)*b^{n-1}\mod\ c ans≡(b−1)∗bn−1mod c，因为b和n的位数特别多，需要高精度减法预处理出(b - 1)和(n - 1)，就可以得到
a n s ≡ { ( ( b − 1 ) % c ) ∗ ( b % c ) n − 1 , if  n − 1 < φ ( c ) ( ( b − 1 ) % c ) ∗ ( b % c ) ( n − 1 ) % φ ( c ) + φ ( c ) , if  ( n − 1 ) ≥ φ ( c ) ans \equiv \begin{cases} ((b - 1)\% c) * (b \% c)^{n - 1},& \text{if $n - 1 < \varphi(c)$}\\ ((b - 1)\% c) * (b \% c)^{(n - 1) \% \varphi(c) + \varphi(c)},& \text{if $(n - 1) \geq \varphi(c)$} \end{cases} ans≡{((b−1)%c)∗(b%c)n−1,((b−1)%c)∗(b%c)(n−1)%φ(c)+φ(c),​if n−1<φ(c)if (n−1)≥φ(c)​
答案就显而易见了。

AC代码：

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL qp(LL a, LL b, LL mod) {LL res = 1;for (; b; b >>= 1, a = a * a % mod) {if (b & 1) {res = res * a % mod;}}return res;
}
LL phi(LL p) {if (p == 1) {return 0;}LL phip = p, q = p;for (int i = 2; i * i <= q; i++) {if (q % i == 0) {phip = phip / i * (i - 1);while (q % i == 0) {q /= i;}}}if (q != 1) {phip = phip / q * (q - 1);}return phip;
}
string calc(string x) {int len = x.size();string ans = "";vector<int> z;for (int i = 0; i < len; i++) {z.emplace_back(x[i] - '0');}z[len - 1]--;for (int i = len - 1; i >= 0; i--) {if (z[i] < 0) {z[i - 1]--;z[i] += 10;}}int first = 0;while (z[first] == 0) {first++;}for (int i = first; i < len; i++) {ans += ('0' + z[i]);}return ans;
}
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);string b, n;LL c;cin >> b >> n >> c;if (c == 1) {cout << "1\n";return 0;}LL phic = phi(c);int len1 = b.size(), len2 = n.size();string bb = calc(b), nn = calc(n);LL b1 = 0, bb1 = 0, c1 = 0;int len3 = bb.size();for (int i = 0; i < len3; i++) {b1 = (b1 * 10 + (bb[i] - '0')) % c;}for (int i = 0; i < len1; i++) {bb1 = (bb1 * 10 + (b[i] - '0')) % c;}int len4 = nn.size();bool ok = true;for (int i = 0; i < len4; i++) {c1 = (c1 * 10 + (nn[i] - '0'));if (c1 >= phic) {ok = false;break;}}if (ok) {c1 = 0;for (int i = 0; i < len4; i++) {c1 = (c1 * 10 + (nn[i] - '0'));}LL ans = b1 * qp(bb1, c1, c) % c;if (ans == 0) {ans = c;}cout << ans << '\n';} else {c1 = 0;for (int i = 0; i < len4; i++) {c1 = (c1 * 10 + (nn[i] - '0')) % phic;}LL ans = b1 * qp(bb1, c1 + phic, c) % c;if (ans == 0) {ans = c;}cout << ans << '\n';}return 0;
}

Exponial

欧拉降幂模板题，只需要求出
n ( n − 1 ) ( n − 2 ) ⋯ 2 1 m o d m n^{(n - 1)^{(n - 2)^{\cdots^{2^{1}}}}}\mod\ m n(n−1)(n−2)⋯21mod m
像这种幂次特别多的，分解一下就是要分别求
( n − 1 ) ( n − 2 ) ⋯ 2 1 m o d φ ( m ) + φ ( m ) ( n − 2 ) ( n − 3 ) ⋯ 2 1 m o d φ ( φ ( m ) ) + φ ( φ ( m ) ) ⋯ (n - 1)^{(n - 2) \cdots^{2^{1}}}\mod\ \varphi(m) + \varphi(m)\\ (n - 2)^{(n - 3) \cdots^{2^{1}}}\mod\ \varphi(\varphi(m)) + \varphi(\varphi(m))\\ \cdots (n−1)(n−2)⋯21mod φ(m)+φ(m)(n−2)(n−3)⋯21mod φ(φ(m))+φ(φ(m))⋯
因为 φ ( m ) \varphi(m) φ(m)经过logm次大概就成为1了，所以这个递归只需要logm次左右，并且要确保 x ≥ φ ( m ) x \geq \varphi(m) x≥φ(m)，x是幂次，来保证扩展欧拉定理的运行，因为 m ≤ 1 0 9 m \leq 10^{9} m≤109，所以当 n ≥ 5 n \geq 5 n≥5时均符合扩展欧拉定理的要求，当 n < 5 n<5 n<5时直接返回模m后的值，因为值都是在可以暴力计算的范围内。

AC代码：

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define int long long
LL qp(LL a, LL b, LL mod) {LL res = 1;for (; b; b >>= 1, a = a * a % mod) {if (b & 1) {res = res * a % mod;}}return res;
}
LL solve(LL n, LL m) {if (n == 1) {return 1 % m;}if (n == 2) {return 2 % m;}if (n == 3) {return 9 % m;}if (n == 4) {return (1 << 18) % m;}if (m == 1) {return 0;}if (n == 0) {return 1;}LL phim = m, q = m;for (int i = 2; i * i <= q; i++) {if (q % i == 0) {phim = phim / i * (i - 1);while (q % i == 0) {q /= i;}}}if (q != 1) {phim = phim / q * (q - 1);}return qp(n, solve(n - 1, phim) + phim, m);
}
signed main() {ios::sync_with_stdio(false);cin.tie(nullptr);LL n, m;cin >> n >> m;cout << solve(n, m) % m << '\n';return 0;
}

再附上几个练习题

Power Tower

上帝与集合的正确用法