快速幂、快速幂取模

在写acm题的时候会碰到求一个数X的N次幂，通常这种题就会要用到快速幂算法。比如求2^n（1<=n<=1000000)。
最开始我想的办法就是用循环暴力求解，简单粗暴。

int ans=1;
for(int i=1;i<=n;i++)
{
   ans*=i;
}
printf("%d\n",ans);

但是这里的n值有10e6.这样求解肯定就时间超限了。所以就我就学习了快速幂。所谓快速嘛。就更快，时间超限的问题不就迎刃而解了。（先了解一下位运算）

位运算

C语言有以上六种位运算。这里我们只要用到按位与（&）和右移运算两种。
按位与&
的口诀就是1&1=1，其余为0。比如求 9&5
0000 1001（二进制数9）
0000 0101（二进制数5）一位一位比较两个数
0000 0001（二进制数1）所以 9&5=1
右移>>
直接举一个例子。求 9>>1
0000 1001（二进制数9）/每一位都向右移动一位/
0000 0001（二进制数1） 所以9>>1=1

快速幂

求2^10=??
首先吧10转化为二进制数为 1010
10=
所以2^10=
从上面两个表达式可以推到出求a^b就只要从左到右一位一位取b的位。每次都让a=a*a，如果碰到了一就把a的值乘到答案里面。直到b为0为止。
快速幂代码实现
（写这个函数的时候P一定要大写。我就因为不小心用的小写困惑了好久）

int Pow(int a,int b)
{
    long long int ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*a;
        a=a*a;
        b=b>>1;
    }
    return(ans);
}

学会了快速幂之后，快速幂取模就比较简单了，只不过要用到应该数学公式，这个直接当作应该定理用就完事了，感觉没必要搞清楚原理，哈哈哈。

快速幂取模

int Pow_mid(int a,int b,int c)
{
    long long int ans=1;
    a=a%c;
    while(b)
    {
        if(b&1)
            ans=(ans*a)%c;
        a=(a*a)%c;
        b=b>>1;
    }
    return(ans);
}

每次运算的时候要作mod c运算，利用的是模运算规则 (a * b) mod c = ((a mod c) * (b mod c)) mod c.