快速幂取模

递归实现：

 1  /*************************************************************************
 2  2     > File Name:        pow_mod.cpp
 3  3     > Author:         wangzhili
 4  4     > Mail:           wangstdio.h@gmail.com
 5  5     > Created Time:   2014年03月17日 星期一 20时59分52秒
 6  6  ************************************************************************/
 7 
 8  7 #include<iostream>          //求解a^i(mod n);
 9  8 typedef long long ll;
10  9 using namespace std;
11 10 ll pow_mod(ll a, ll i, ll n){
12 11     if(i == 0) return 1 % n;
13 12     int temp = pow_mod(a, i >> 1, n);
14 13     temp = temp*temp%n;
15 14     if(i&1) temp = temp*a%n;
16 15     return temp;
17 16 }
18 17 
19 18 int main(){
20 19     ll n, i, a;
21 20     while(cin >> a >> i >> n){
22 21         cout << pow_mod(a, i, n) << endl;
23 22     }
24 23     return 0;
25 24 }
26

非递归实现

 1 #include<iostream>
 2 using namespace std;
 3 typedef long long ll;
 4 ll pow_mod(ll a, ll i, ll n){
 5     ll ans = 1, temp = a;
 6     while(n){
 7         if(n & 1){
 8             ans = (temp * ans) % n;
 9         }
10         temp *= temp;
11         temp %= n;
12         n >> 1;
13     }
14     return ans;
15 }