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

提示：

• 1 <= n <= 1015

方法一：快速幂

思路与算法

对于偶数下标处的数字，它可以为 0, 2, 4, 6, 8 共计 5 种，而长度为 n 的数字字符串有 \lfloor \dfrac{n+1/2} \rfloor 个偶数下标，其中 \lfloor x \rfloor 表示对 x 向下取整。

对于奇数下标处的数字，它可以为 2, 3, 5, 7 共计 4 种，而长度为 n 的数字字符串有 \lfloor \dfrac{n}{2} \rfloor 个奇数下标。

因此长度为 n 的数字字符串中，好数字的总数即为：

5^{\lfloor n+1/2} \rfloor} \cdot 4^{\lfloor n}{2} \rfloor}

在本题中，由于 n 的取值最大可以到 10^{15，如果通过普通的乘法运算直接求出上式中的幂，会超出时间限制，因此我们需要使用快速幂算法对幂的求值进行优化。

快速幂算法可以参考「50. Pow(x, n)」的官方题解 。

代码

[sol1-C++]

class Solution {
private:
    static constexpr int mod = 1000000007;
    
public:
    int countGoodNumbers(long long n) {
        // 快速幂求出 x^y % mod
        auto quickmul = [](int x, long long y) -> int {
            int ret = 1, mul = x;
            while (y > 0) {
                if (y % 2 == 1) {
                    ret = (long long)ret * mul % mod;
                }
                mul = (long long)mul * mul % mod;
                y /= 2;
            }
            return ret;
        };
        
        return (long long)quickmul(5, (n + 1) / 2) * quickmul(4, n / 2) % mod;
    }
};

[sol1-Python3]

class Solution:
    def countGoodNumbers(self, n: int) -> int:
        mod = 10**9 + 7
        
        # 快速幂求出 x^y % mod
        def quickmul(x: int, y: int) -> int:
            ret, mul = 1, x
            while y > 0:
                if y % 2 == 1:
                    ret = ret * mul % mod
                mul = mul * mul % mod
                y //= 2
            return ret
            
        return quickmul(5, (n + 1) // 2) * quickmul(4, n // 2) % mod

复杂度分析

• 时间复杂度：O(\log n)。

• 空间复杂度：O(1)。