题解 UVA374 【Big Mod】
TRZ_2007
2020-01-10 18:33:23
其实UVA的重题率是很高的……
## Solution
主体思路：快速幂（不知道的不要慌）
**怎么用呢？**（会快速幂的可以跳过直接看代码）
先从初一的数学讲起……
我们都知道这样的一个式子：
$$a^b= \sqrt{a} ^b \times \sqrt{a}^b = a^ \frac{b}{2} \times a^ \frac{b}{2}$$
这也许是你认识乘方第一个定理。接下来我们把注意力放在$a^ \frac{b}{2}$上，有没有发现它的指数和$a ^ b$的**指数在形式上是一样**的？
于是我们用**分治**的方法来解决（不会的可以撤了）
定义函数$f(a,b,c) = a^b \mod c$，由数学知识得：
$$f(a,b,c) = f(a,\frac{b}{2},c) \times f(a,\frac{b}{2},c)$$
好了，接下来令$\dfrac{b}{2}=b$（就是程序的赋值），则函数可以继续递归。成立。
但是有一个问题：$b$**是奇数怎么办**？
很简单，在答案上乘个$a$，$b$就变成偶数了。
## 代码（总算上来了）
```cpp
#include <bits/stdc++.h>
using namespace std;
long long b,p,Mod;
void solve() {
long long ans = 1;
while(p) {
if(p & 1) ans = (ans * b) % Mod;
p >>= 1;
b = (b * b) % Mod;
}
printf("%lld\n",ans % Mod);
}
int main() {
while(scanf("%lld %lld %lld",&b,&p,&Mod) != EOF) {
solve();
}
}
```
这里的是非递归版的，递归版的可以自己去试试看