算法篇————快速幂

        

2016-09-15

今天介绍第二种算法,快速幂的使用,这个极大的方便了数值较大的数的之间的运算。

快速幂取模

假如我们要求a^b,而b是一个非常大的数的话,我们就可以用到快速幂的算法。这样复杂度不高,不会超时。

假如求 a ^ n 次方

我们可以把 n 表示为 2^k1 + 2^k2 + 2^k3….,可以证明所有数都可以用前式来表示。(其实就是二进制表示数的原理)

那么 a^n = a^2^k1 a^2^k2 a^2^k3……

那么就可以利用二进制来加快计算速度了。

假如 a^22 , 22转化为二进制为 10110, 即 a^22 = a^16 a^4 a^2;

那么是不是可以在O(logn)的复杂度求解。

下面是代码实现:(特别注意避免大数超出范围,用long long 存中间值)

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef long long LL;
LL fun(LL x,LL n,)
{
LL res=1;
while(n>0)
{
if(n & 1)
res=(res*x)%Max;
x=(x*x)%Max;
n >>= 1;
}
return res;
}

矩阵快速幂

前面是数与数之间的幂运算,对于矩阵与矩阵的幂运算,也可以用到快速幂的解决办法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/*===================================*/
|| 快速幂(quickpow)模板
|| P 为等比,I 为单位矩阵
|| MAX 要初始化!!!!
||
/*===================================*/
/*****************************************************/
#include <cstdio>
const int MAX = 3;
typedef struct{
int m[MAX][MAX];
} Matrix;
Matrix P = {5,-7,4,
1,0,0,
0,1,0,
};
Matrix I = {1,0,0,
0,1,0,
0,0,1,
};
Matrix matrixmul(Matrix a,Matrix b) //矩阵乘法
{
int i,j,k;
Matrix c;
for (i = 0 ; i < MAX; i++)
for (j = 0; j < MAX;j++)
{
c.m[i][j] = 0;
for (k = 0; k < MAX; k++)
c.m[i][j] += (a.m[i][k] * b.m[k][j])%9997;
c.m[i][j] %= 9997;
}
return c;
}
Matrix quickpow(long long n)
{
Matrix m = P, b = I;
while (n >= 1)
{
if (n & 1)
b = matrixmul(b,m);
n = n >> 1;
m = matrixmul(m,m);
}
return b;
}
/*************************************/
int main()
{
Matrix re;
int f[3] = {2,6,19};
long long n;
while (scanf("%I64d",&n) && n != 0)
{
if (n == 1)
printf("1\n");
else if (n <= 4)
printf("%d\n",f[n-2]);
else {
re = quickpow(n - 4);
printf("%d\n",(((re.m[0][0]*f[2])
+ (re.m[0][1]*f[1]) + (re.m[0][2]*f[0])) %9997 + 9997) % 9997);
}
}
return 0;
}