这就是快速幂的计算方式，将一个幂次方计算公式拆分后计算
这一题就是典型的快速幂的模板题，前几天因为写题遇到了知识盲区所以弄了很久，昨天的困难题也没做出来，只有自己的计算思路，实现还跑不出来，气死我了，今天也刚刚学会了快速幂
对于本题我们可以对答案进行拆分，分为两部分，一个计算偶数下标的幂次方，一个计算奇数下标的幂次方
偶数有0，2，4，6，8；一共5个
质数有2，3，5，7；一共4个
所以偶数下标计算5的幂次方
奇数计算4的幂次方
位数由n决定
而位数n对应的偶数下标个数为(n+1)/2奇数小标个数为n/2
而遍历的幂次方根据二进制的位运算进行遍历拆分幂次方计算(n&1)>0,只有1和0两种情况
class Solution {private static final int MOD = 10_0000_0007;public int countGoodNumbers(long n) {return (int)(pow(5,(n+1) / 2)*pow(4,n / 2) % MOD);}public long pow(long x,long n){long res = 1;while(n>0){if((n&1)>0){res = res*x%MOD;}x = x*x%MOD;n = n>>1;}return res;}}
)