次方求模、二分幂，快速幂，矩阵快速幂，快速乘

1.二分幂

要求 a^n，如果知道了 a^(n/2) 次方的话，再来个平方就可以了。 即 如果n是偶数，则A=a^(n/2) ； A=A*A.。 如果n是奇数 , 则A=a^((n-1)/2) ； A=a*A*A。 这就一下子差不多就节省了n/2-1次乘法运算 那么按照这个思路就能运用分治的思想,那么复杂度就有原来的O(n)，降低为O(lgn)。

long long int pow(int a,int n)//求a的n次幂
{
    if (n==0)
        return 1;
    if (n==1)
        return a;
    long long int ans=pow(a,n/2);//从函数的功能区理解递归
    ans*=ans;
    if (n%2==1)
        ans*=a;
    return ans;
}

2.快速幂算法

快速幂 , 矩阵快速幂 在算大指数次方时是很高效的，他的基本原理是二进制。快速乘也是用了二进制。 大家首先要认识到这一点：任何一个整数N，都能用二进制来表示。。 那么对于a^n ， n一定可以用二进制表示。 比如a^156,而156(10)=10011100(2) 那么 A=a156=a10011100a156=a10011100 =a27∗1+26∗0+25∗0+24∗1+23∗1+22∗1+21∗0+20∗0a27∗1+26∗0+25∗0+24∗1+23∗1+22∗1+21∗0+20∗0 =(a27∗1)∗(a26∗0)∗(a25∗0)∗(a24∗1)∗(a23∗1)∗(a22∗1)∗(a21∗0)∗(a20∗0)(a27∗1)∗(a26∗0)∗(a25∗0)∗(a24∗1)∗(a23∗1)∗(a22∗1)∗(a21∗0)∗(a20∗0) 我们就按照这个公式来求解a^156，原来要进行156-1=155次乘法运算，现在的差不多运算次数就是他 二进制的长度二进制中1的个数=84=24次

long long int fun( int a, int b ) 
{
    long long int ans = 1;
    int base = a;
    while( b != 0 ) 
    {
        if(b & 1)//判断奇偶性
        {
            ans *= base;
        }
         base *= base; //注意：a^{2^7}=a^{2^6} * a^{2^6} ，而不是 a^{2^7}=a^{2^6} * a ，所以这是对的。
        b /= 2;//与b=b>>1相同
    }
    return r;
}

3.矩阵快速幂算法

其实用的更多是使用矩阵快速幂，算递推式，注意是递推式 ，比如 f(n)=a*f(n-1)+b*f(n-2)，简单的如斐波那契数列的第一亿项的结果模上10000000后是多少你还能用递推式去，逐项递推吗？当然不能，这里就可以发挥矩阵快速幂的神威了，那斐波那契数列和矩阵快速幂能有一毛钱的关系？答案是有而且很大 对于f(n)=a*f(n-1)+b*f(n-2) ， 我们可以考虑矩阵这种数学工具,构造矩阵

这样求f(n),f(n-1) 就相当于求左边矩阵的n-2次幂。这个时候就可以用上面的快速幂来计算了。 代码与快速幂类似，只是实数乘法变成了矩阵乘法。用个函数写就行了。

4.快速乘

求a*b%m , 当a*b结果很大，乘完后可能会移除。 可以用二进制来实现快速乘算法。 以前十进制的乘法是： 123*567=123*5*100 + 123*6*10 + 123 * 7 * 1 这里100，10，100100 都是十进制 的进制位数。那么如果考虑二进制的话，我们任选其他任意二进制数，就有 1001101∗11010=1001101∗2^4∗1+1001101∗2^3∗1+1001101∗2^2∗0+1001101∗2^1∗1+1001101∗20∗01001101∗11010=1001101∗24∗1+1001101∗23∗1+1001101∗22∗0+1001101∗21∗1+1001101∗20∗0 我们对上面的每一个加项进行取模，在加起来，就不会溢出了。

long long int fun(long long int a ,long long int b , long long int m)
{
    int sum=0;
    int k=1;
    while(b)
    {
       if(b&1)
    {
        sum=(sum+a*k)%m;
    }
    k=(k*2)%m;
    b=b/2;
}
}