You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

184 lines
4.7 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

## [指数循环节&欧拉降幂](https://blog.csdn.net/acdreamers/article/details/8236942)
### 一、问题
比如计算 $$\large A^B \ \% \ C$$
其中$1 \leq B \leq 10^{20000000}$ 和 $1 \leq C \leq 10^6$
$b$过大,使用暴力和快速幂是无法求解的。
### 二、扩展欧拉定理公式
- ① 当$B \geq \phi(C)$时:
$$\large A^B \% C = A^{B \% \phi(C)+\phi(C)} \% C $$
> 这是广义降幂公式,不要求$A$与$C$互质!
- ② 当$B<φ(C)$时,就没有降幂的必要了
### 三、练习题
**[$P5091$ 【模板】扩展欧拉定理](https://www.luogu.com.cn/problem/P5091)**
**题意**
给定$A$,$B$和$C$的值,求$A^B \ mod \ C$的值。其中$1 \leq A,C \leq 10^9,1 \leq B \leq 10 ^{1000000}$。
**特点**
欧拉降幂,模板题
```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int N = 2000010;
// 求单个数字的欧拉函数
int phi(int x) {
int 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);
return res;
}
// 快速幂
int qmi(int a, int b, int p) {
int res = 1;
a %= p;
while (b) {
if (b & 1) res = res * a % p;
b >>= 1;
a = a * a % p;
}
return res;
}
signed main() {
int a, c;
cin >> a >> c;
int p = phi(c);
// 将非数字字符,比如空格读没
char ch;
ch = getchar();
while (ch < '0' || ch > '9') ch = getchar();
// 当是数字字符时,一直读入
int b = 0;
while (ch >= '0' && ch <= '9') {
b = b * 10 + ch - '0';
if (b >= p) // 检查b是否大于等于phi(c)
b = b % p + p;
// 继续读入下一个字符
ch = getchar();
}
printf("%lld\n", qmi(a, b, c)); // 按快速幂来计算就行了
}
```
**[$HDU2837$ $Calculation$](https://acm.hdu.edu.cn/showproblem.php?pid=2837)**
**题意**$f(0) = 1$ $and$ $0^0=1$. $f(n) = (n\%10)^{f(n/10)}$ 求$f(n)\%m$。
就递归加指数循环节,
$$\large f(n)\%m = (n\%10)^{f(n/10)\% \phi(m)+ \phi(m)}\%m$$
然后继续计算一下指数部分:
$f \large (n/10)\%\phi(m)=(n/10\%10)^{f(n/10/10)\%\phi(\phi(m))+\phi(\phi(m))}\%\phi(m)$
一层层递归,直到$n==0$的话,此时$0^0=1$,就返回$1\%$当前要$mod$的那个数了,
我们设当前$dfs$到的层中表达式为$f(x)$,当前的$\phi$为$\phi(y)$,
我们需要判断$f(x)$是不是大于$phi(y)$,如果大于则用扩展欧拉定理进行进步化化简,否则直接计算。
```cpp {.line-numbers}
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
// 求单个数字的欧拉函数
int phi(int x) {
int 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);
return res;
}
// 快速幂
int qmi(int a, int b, int p) {
int res = 1;
a %= p;
while (b) {
if (b & 1) res = res * a % p;
b >>= 1;
a = a * a % p;
}
return res;
}
// a^b 与 c 谁大谁小?
// 返回 a^x<=c的第一个a^x,其中x ∈ [1,b]
// 如果跑完b还是 a^b <=c, 就返回 a^b
int check(int a, int b, int c) {
int res = 1;
while (b--) {
res *= a;
if (res >= c) return res;
}
return res;
}
int dfs(int a, int c) {
if (a == 0) return 1;
int p = phi(c);
// f(n/10)
int x = dfs(a / 10, p);
int y = check(a % 10, x, c);
if (y >= c) {
int res = qmi(a % 10, x + p, c);
if (res == 0) res += c;
return res;
} else
return y;
}
signed main() {
int T;
cin >> T;
while (T--) {
int a, c;
cin >> a >> c;
cout << dfs(a, c) % c << endl;
}
}
```
> <font color='red' size=4><b>注:这个代码没看懂,$TODO$,待续</b></font>
[$HDU4335$ $What$ $is$ $N?$](https://acm.hdu.edu.cn/showproblem.php?pid=4335)
题意:给定$3$个整数$b,p,M$,其中$0 \leq b <p,1 \leq p \leq 10^5 $和$1 \leq M \leq 2^{64}-1$,求满足下面两个条件的$n$ 的个数。
![](https://dsideal.obs.cn-north-1.myhuaweicloud.com/HuangHai/BlogImages/202311151419918.jpeg)
**分析**
由$$\large n ^{n! \% \phi(p)+\phi(p)} \% p \equiv b$$
所以这样就容易多了,注意有个特判。
BZOJ3884: 上帝与集合的正确用法
https://www.cnblogs.com/jiecaoer/p/11442358.html
TODO 挖坑等填
https://www.cnblogs.com/LMCC1108/p/11252888.html