2021-09-26

对于像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)
a¹¹= a⁸+ a²+ a¹
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;
}

快速幂常常涉及到大数，这样的题目通常还会使用取模操作
这里，aⁿmod m=(a mod m)ⁿ mod m

 if(n&1) 
    r = (t*r) % mod ;
  t = (t*t) % mod;

矩阵快速幂：

运用了线性代数的知识矩阵乘法.