对于像Java也不能处理的大数,存在的问题:一数字大,二计算时间长
对于幂数来说,很容易想到快速幂的办法来解决:
int f(int a,int n) { if(n==1) return 0; int t=f(a,n/2); //分治 if(n%2==1) //奇数情况 return t*t*a; else return t*t;//偶数情况 }
更好的一种位运算做快速幂,时间复杂度也是O(log2 n)
a11= a8+ a2+ a1
11: 1011 (二进制)
11= 8+0+2+1
这个判断利用二进制的位运算很容易判断:
1)n&1,取最后一位,并判断是否是0
2)n>>1,把n右移一位,去掉n的最右面的一位
int f(int a,int n) { int t=a;//不定义也可以 int r=1;//返回结果 while(n) { if(n&1) r*=t;//如果n的这个地方是1,就需要乘以 t*=t;//2,4,8,,, n>>1;//去掉刚刚处理过的一位 } return r; }
快速幂常常涉及到大数,这样的题目通常还会使用取模操作
这里,anmod m=(a mod m)n mod m
if(n&1) r = (t*r) % mod ; t = (t*t) % mod;
矩阵快速幂:
运用了线性代数的知识矩阵乘法.