浅谈欧拉定理及其扩展
欧拉定理
欧拉定理其实是费马小定理的一个推广，首先来回顾一下费马小定理。
费马小定理
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
上帝与集合的正确用法