分治算法(Divide and Conquer Algorithms)

所谓分治算法，就是把问题分而治之的意思，将一个较大的问题分解成几个较小的问题，然后通过对较小的问题进行求解，达到对整个问题的求解。我们在搜索中用到的二分法，排序中有到的快速排序和归并排序，都是分治算法的应用。

例题：取余运算(mod)
输入x,p,k的值，求xp mod k的值。其中x,p,k都长整型数
例如：
输入：3 5 7 输出：5

提示1：若p为偶数， 若p为奇数，
提示2：(a*b)%p=(a%p*b%p)%p

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;

int x,p,m,i,result;
int main(){
    cin>>x>>p>>m;
    result=1;
    while (p>0)
    {
        if (p%2==1)
           result=result*x%m;
           p/=2;
           x=x*x%m;
    }
    cout<<result<<endl;
    return 0;    
}