取余运算（mod）（分治）

【问题描述】

       输入b，p，k的值，求bp mod k的值。其中b，p，k*k为长整形数。

【输入样例】mod.in

       2 10 9

【输出样例】mod.out

       2^10 mod 9=7

题目的只要特点是数据过大，

下面先介绍一个原理：A*B%K = (A%K )*(B% K )%K。显然有了这个原理，就可以把较大的幂分解成较小的；

因为是2的10次方数据过大，那有什么办法可以把数据给拆开呢？2的10次方，为两个2的5次方的乘积，而2的5次方又可以

分解为两个2的2次方和一个2的一次方的乘积，利用上述的原理，我们只需要把拆开的数进行模运算就可以，这与大数进行模运算方法相同，

而且拆开的每个数模运算完成之后就可以计算出大数的结果，所以算法是分治。

【代码】

#include<iostream>

#include<cstdio>

#include<cstdlib>

using namespace std;

int b,p,k;

int f(int);

int main()

{

    scanf("%d%d%d",&b,&p,&k);

    b%=k;//防止b过大

    cout<<f(p);

    return ;

 }

int f(int x)

{

    if(x==)return ;//任何数的0次方模k都等于1

    int tmp=f(x/)%k;//a*b%k=a%k*b%k%k;

    tmp=(tmp*tmp)%k;

    if(x%==)tmp=(tmp*b)%k;

    return tmp;

}