关于快速幂

快速幂是个快速计算幂次的算法，原理很简单：

a^b=a*a*a*a*a*......*a (b个a 相乘) 如果直接计算要做 b-1 次乘法。

可以利用幂运算的性质: a^b=(a^c)*(a^d)=a^(c+d) 其中b=c+d

如果把b平均分为两份，每份的数量为c=d=b/2, a^c和a^d的值一样，就可以重复利用。

这样分一次就只要做 b/2-1+1=b/2次的乘法，若b为奇数，则要做b/2+1次乘法，于是乘法的次数就大大减少，

这样重复分几次后，原式的值就能很快地算出来。

用递归的代码:

1 int QuickPow(int a,int b)
2 {
3      if (b==1) return a;
4      if (b&1) return QuickPow(a,b-1)*a;   //b为奇数
5      return QuickPow(a,b/2);
6 }

非递归：

 1 int QucikPow(int a,int b)
 2 {
 3     int ans=1;
 4     while (b)
 5     {
 6          if (b&1) ans=ans*a;
 7          b=b>>1;
 8          a=a*a;
 9      }
10     return ans;
11 }

注意事项：

1.用递归的方法会好理解点，但如果b很大的话递归会爆栈。

2. 函数返回值可能会溢出，如题目要求可利用模运算规则：(a*b)%m=(a%m*b%m)%m

3. 就算取模了，算法中有乘法操作的地方也还可能会溢出，这就要用快速幂的变式：

快速加法： a*b=a*(b/2)+a*(b/2)

(a+b)%m=(a%m+b%m)%m

这样就不会溢出了。（还是在tyvj p2043 发现的,下面附上AC代码）

 1 #include <stdio.h>
 2 unsigned long long p,m,n;
 3 unsigned long long ans=1;
 4 inline unsigned long long quickadd(unsigned long long a,unsigned long long m)
 5 {
 6    unsigned long long ans=0;
 7    while (a)
 8    {
 9        if (a&1) ans=(ans+m)%p;
10        a=a>>1;
11        m=(m*2)%p;
12    }
13    return ans;
14 }
15 void quick(unsigned long long n)
16 {
17   while (n)
18   {
19       if (n&1) ans=(quickadd(ans,m))%p;
20       n=n>>1;
21       m=(quickadd(m,m))%p;
22   }
23 }
24 
25 int main()
26 {
27   scanf("%I64d%I64d%I64d",&n,&m,&p);
28   ans=m%p;
29   m=m-1;
30   m=m%p;
31   quick(n-1);
32   printf("%I64d\n",ans);
33 }