1922. 统计好数字的数目-暴力解法和快速幂法

1922. 统计好数字的数目

我们称一个数字字符串是 好数字 当它满足（下标从 0 开始）偶数 下标处的数字为 偶数 且 奇数 下标处的数字为 质数 （2，3，5 或 7）。

比方说，"2582" 是好数字，因为偶数下标处的数字（2 和 8）是偶数且奇数下标处的数字（5 和 2）为质数。但 "3245" 不是 好数字，因为 3 在偶数下标处但不是偶数。

给你一个整数 n ，请你返回长度为 n 且为好数字的数字字符串 总数 。由于答案可能会很大，请你将它对 109 + 7 取余后返回 。

一个 数字字符串 是每一位都由 0 到 9 组成的字符串，且可能包含前导 0 。

示例 1：

输入：n = 1
输出：5
解释：长度为 1 的好数字包括 “0”，“2”，“4”，“6”，“8” 。

示例 2：

输入：n = 4
输出：400

示例 3：

输入：n = 50
输出：564908303

暴力解法

 if(n==1){
        return 5;
    }
    for(int i=0;i<n;i++){
        if(i%2==0){
                re=re*5;
        }
        else{
            re=re*4;
        }
        re=re%1000000007;
    }

快速幂法：

long long mypow(long long x,long long n){
  
    long long mul=x;
     long long re=1;
    while(n>0){
          if(n%2==1){
                n=(n-1)/2;
               re=re*mul%1000000007;
          }
          else{
              n=n/2;
          }
            mul=mul*mul%1000000007;
         
        
  }
  
  return re;
        
    

}

int countGoodNumbers(long long n){

  
  
    return mypow(5,n-n/2)*mypow(4,n/2)%1000000007;



}