sae wordpress 伪静态/seo资源

经常碰到要求(a^b )%c的题目，这个时候a,b,c一般都在int范围内，但是a^b可能就超出int表示的范围了。

这个时候要快速求解(a^b )%c可以采用快速幂模运算，基本原理如下：

(a*b)modc=(amodc*bmodc)modc

(a*b)modc=(amodc*b)modc

(a*b)modc=(a*bmodc)modc

所以可以用递归来实现快速幂模运算，代码如下：

#include <iostream>
#include <iomanip>
#include <cmath>
#define PI 3.1415927
using namespace std;//快速幂模运算 (a^n)%m
int pow_mod(int a, int n, int m) {if(n==0) return 1;int x = pow_mod(a, n/2, m);long long ans = (long long)x*x%m;if(n%2==1) ans = ans*a%m;return (int)ans;
}int main()
{int n, m;while(cin>>n>>m) {if(n==0&&m==0) break;cout << pow_mod(n, m, 1000) << endl;}return 0;
}