初学算法之快速幂

　　目前遇到需要用快速幂的题，大多都是与取模有关且直接乘会爆数据的题。

　因此，在讲快速幂之前，我们得先了解下取模运算。

基本性质

若p|(a-b)，则a≡b (% p)。例如 11 ≡ 4 (% 7)， 18 ≡ 4(% 7)
(a % p)=(b % p)意味a≡b (% p)
对称性：a≡b (% p)等价于b≡a (% p)
传递性：若a≡b (% p)且b≡c (% p) ，则a≡c (% p)

取模运算运算规则

模运算与基本四则运算有些相似，但是除法例外。其规则如下：

(a + b) % p = (a % p + b % p) % p （1）
(a - b) % p = (a % p - b % p) % p （2）
(a * b) % p = (a % p * b % p) % p （3）
a ^ b % p = ((a % p)^b) % p （4）

结合律：

((a+b) % p + c) % p = (a + (b+c) % p) % p （5）

((a*b) % p * c)% p = (a * (b*c) % p) % p （6）

交换律：

(a + b) % p = (b+a) % p （7）

(a * b) % p = (b * a) % p （8）

分配律：

(a+b) % p = ( a % p + b % p ) % p （9）

((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p （10）

取模运算重要定理

若a≡b (% p)，则对于任意的c，都有(a + c) ≡ (b + c) (%p)；（11）
若a≡b (% p)，则对于任意的c，都有(a * c) ≡ (b * c) (%p)；（12）
若a≡b (% p)，c≡d (% p)，则 (a + c) ≡ (b + d) (%p)，(a - c) ≡ (b - d) (%p)，

(a * c) ≡ (b * d) (%p)，(a / c) ≡ (b / d) (%p)；

红字部分是快速幂经常会用到的，快速幂用到的思想很多博客中都有解释，这里就大致总结下代码。

int pmod(int a)  //快速幂
{
    int b=a;
    int ans=1;
    a=a%c;
    while(b)
    {
        if(b&1)  //或b%2
        ans=(ans*a)%c;
        b>>=1; //或b/=2;
        a=(a*a)%c;
    }
    return ans;
}

 1 long long mmod(long long a,long long b,long long c)  //快速乘法
 2 {
 3     long long res=0;
 4     while(b)
 5     {
 6         if(b&1)
 7         res=(res+a)%c;
 8         b>>=1;
 9         a=(a+a)%c;
10     }
11     return res;
12 }
13 long long pmod(long long a,long long b,long long c)
14 {
15     long long ans=1;
16     while(b)
17     {
18         if(b&1)
19         ans=mmod(ans,a,c)%c;
20         b>>=1;
21         a=mmod(a,a,c)%c;
22     }
23     return ans;
24 }

View Code

 1 //poj 3070 斐波那契数列
 2 #include<iostream>
 3 #include<cstdio>
 4 #include <cstring>
 5 using namespace std;
 6 const int mod = 10000;
 7 struct nod
 8 {
 9     int nu[2][2];
10 }a,ans;
11 int n;
12 nod mul(nod a,nod b)
13 {
14     nod t;
15     memset(t.nu,0,sizeof(t.nu));
16     for(int i=0;i<2;i++)
17         for(int j=0;j<2;j++)
18         {
19             for(int k=0;k<2;k++)
20             {
21                 t.nu[i][j]+=(a.nu[i][k]*b.nu[k][j])%mod;
22                 t.nu[i][j]%=mod;
23             }
24         }
25     return t;
26     
27 }
28 void qm(int n)
29 {
30     a.nu[0][0]=a.nu[0][1]=a.nu[1][0]=1;a.nu[1][1]=0;
31     ans.nu[0][0]=ans.nu[1][1]=1;
32     ans.nu[1][0]=ans.nu[0][1]=0;
33     while(n)
34     {
35         if(n&1) ans=mul(a,ans);
36         n>>=1;
37         a=mul(a,a);
38     }
39 }
40 int main()
41 {
42     while(scanf("%d",&n))
43     {
44         if(n==-1)return 0;
45         
46         qm(n);
47         printf("%d
",ans.nu[1][0]);
48     }
49 }

View Code

具体的这个博客写的挺不错：http://www.cnblogs.com/luruiyuan/p/5570756.html

这个是一位大佬对快速幂的推导思路：https://wenku.baidu.com/view/2384ecc02cc58bd63186bdf6.html