算法--分治--a^b%m

    杭电上有一道十分让初学者十分蛋疼的题 a^b%m，看似很简单，但题目要求b的范围是(0,1000000000],a是32位整数范围，m是小于40000的整数。咋一看这题，貌似要用高精度。但是赤裸裸的用高精度的话，在空间复杂度以及时间复杂度上都是伤不起的！！
    让我们来换个思路，有一定数学基础的人都知道，(a*b)%m 是等价于 a%m * b%m的，这样好了，可以不用高精度了，但是完全模拟的话，在规定时间内是不可能出解的。
    我们再想想，是否可以减小计算量呢？有了！我们可以将 a^b 分解成为 t1*a^1+t2*a^2+t3*a^3+.....(ti=0 或者 1),我们预处理下,算出a^2i,然后将b变为二进制，乘以相应的项，我们就得到了最后的结果。运算次数大大减少了，这样是可以在规定时间内出解的。
    如果我们觉得上面的方法太麻烦的话，下面的递归代码就十分简单了。

#include<iostream>
using namespace std;
int run(int a,int b,int m){
    int t;
    if (b==1) return a%m;
    if (b&1){
        t=run(a,b/2,m);
        return ((t*t%m)*a)%m;   
    }else{
        t=run(a,b/2,m);
        return (t*t)%m;      
    }
}
int main(){
    int a,b,m;
    cin >> a >> b >> m ;
    cout << run(a,b,m);
    system("pause");
    return 0;    
}

    这其实是利用了一个分治的思想，要想求a^b1,先求出a^b2（其中b2=b1/2），而要求a^b2，又得求出a^b3（其中b3=b2/2）..........直到bi =1。整个问题的时间复杂度就变得非常低了。最多几十次基本操作就能得到结果（有木有感觉很神奇）。其实我们还可以将这个算法求斐波拉契数列的第10000000项对m取余，这样用到矩阵的乘法，下面给出具体的矩阵推导以及代码。

#include<iostream>
using namespace std;
class Matrix{
public: 
      int width,height;
      Matrix(){        
      }
      Matrix(int hei,int wid){
         width = wid; height = hei; 
         v = new int*[height];
           for (int i=0;i<height;i++)
              v[i] = new int[width];          
      }
      void set(int hei,int wei){
           v = new int*[height];
           for (int i=0;i<height;i++)
              v[i] = new int[width];
      }
      int** v;
      friend Matrix operator*(Matrix a,Matrix b){
         Matrix res(a.height,a.width);
         //确保数据正确 
         //if (a.width!=b.height) retutn res;
         for (int i=0;i<a.height;i++){
            for (int j=0;j<a.width;j++){
                int ans = 0;
                for (int k=0;k<a.width;k++){
                    ans += a.v[i][k]*b.v[k][j];
                }
                res.v[i][j] = ans;
            }    
         }
         return res;
      };
      friend Matrix operator%(Matrix a,int m){
         Matrix ans(a.height,a.width);
         for (int i=0;i<a.height;i++)
            for (int j=0;j<a.width;j++)
                ans.v[i][j] = a.v[i][j] % m;
         return ans;     
      }
};
Matrix a(2,2);
Matrix run(int b,int m){
    Matrix t;
    if (b==1) return a%m
    ;
    if (b&1){
        t=run(b/2,m)%m;
        return ((t*t)*a)%m;   
    }else{
        t=run(b/2,m)%m;
        return (t*t)%m;      
    }
}
int main(){
    int n,m;
while(1){
    cin >> n >> m;
    a.v[0][0] = 0; a.v[0][1] = 1; a.v[1][0] = 1; a.v[1][1] = 1; 
    Matrix ans;
    ans = run(n,m);
    for (int i=0;i<ans.height;i++){
       for (int j=0;j<ans.width;j++)
          cout << ans.v[i][j] << " ";
       cout << endl;   
    }
}
    system("pause");
    return 0;    
} 

    分治就是分而治之的缩写，分治的思想并不局限于这道题，它能极大的提高算法的效率。所以掌握它是十分必要的。

评论

1 楼 sawadari_k 2013-08-23  

好文，没人顶的话。我来顶一个。