题目

已知今天是星期六，请问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;
}

总结

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

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