快速幂（非递归）

小鱼儿 2024-03-30 13:27 79阅读 0赞

## 数论——快速幂 ##

`记录一道关于数论的题目，题目本身不难，主要是学习一下思想~`

--------------------

#### 文章目录 ####

*  数论——快速幂
 *  题目
 *  常规思路(非比赛时使用)
 *  快速幂解题（比赛推荐）
 *  总结

--------------------

## 题目 ##

> 已知今天是星期六，请问20^22天后是星期几？  
> 注意用数字1到7表示星期一到星期日。

## 常规思路(非比赛时使用) ##

> 如果大家用java写算法的话，我们知道有这么一个数学类的函数Math.pow(a, b);它能计算a的b次方，并以double类型返回结果，此时我们只需要用得到的结果取模7即可，  
> 代码如下（Java）：

public class Main{
        
       public static void main(String[] args) {
        
           double pow = Math.pow(20, 22);
            int v = (int) pow % 7;
            System.out.println(v + 6);
        }
    }

> 虽然这样也能做，但是还有更优解，我们利用二进制来优化题解。

## 快速幂解题（比赛推荐） ##

> **解题思路：**  
> 快速幂的思想：  
> ①把指数想象成二进制的表示方式；  
> ②如果指数不等于0，则判断最后一位是否为1（&），如果是，则用结果变量result 乘 底数 并取模（根据题意设定模的大小），否则不能乘，因为0 \* result = 0；  
> ③每进行一次，底数 = 底数 \* 底数 % 模 （将指数表示为二进制之后，底数应该对应每次的指数），  
> 即 a的1次 a的2次 a的4次 a的8次 （同底数相乘，指数相加，正好对应二进制的每一位），  
> 例如：20的3次方（3的二进制为11）= 20的（2的1次方）次方 \* 20的（2的0次方）次方；  
> ④将指数往右边移动一位，方便进行下一次的判断  
> ⑤其实到这里，快速幂的思想分析已然结束，但是格外的取模操作让人感到不太理解（不考虑数据溢出的情况下可以不取模），为什么每次都可以取模？其实只要是乘法，不论何时取模都是一样的，可以参考 以下公式：  
> 例如：（a \* b）% c = (a % c) \* (b % c); --> (5 \* 6) % 4 = ( 5 % 4) \* (6 % 4) = 2  
> 代码如下（Java）：

import java.io.*;
    
    public class Main {
        
        static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        static int mod = 7;
    
        public static void main(String[] args) throws IOException {
        
            bw.write(String.valueOf(FastPower(20, 22) + 6));
            bw.flush();
            bw.close();
        }
        
        public static int FastPower(int a, int b) {
        
        int res = 1;
        while (b != 0) {
        
            if ((b & 1) == 1) {
        //如果满足条件，则相乘
                res = res * a % mod;
            }
            //无论如何，a都要不断倍增，b都要不断右移
            a *= a % mod;
            b = b >> 1;
        }
        return res;
    }

--------------------

## 总结 ##

`快速幂是经典的数论题目，通过二进制和取模的方式，极大的简化了计算！`

文章粗浅，希望对大家有帮助！