原文链接: https://leetcode-cn.com/problems/count-good-numbers

英文原文

A digit string is good if the digits (0-indexed) at even indices are even and the digits at odd indices are prime (2, 3, 5, or 7).

• For example, "2582" is good because the digits (2 and 8) at even positions are even and the digits (5 and 2) at odd positions are prime. However, "3245" is not good because 3 is at an even index but is not even.

Given an integer n, return the total number of good digit strings of length n. Since the answer may be large, return it modulo 109 + 7.

A digit string is a string consisting of digits 0 through 9 that may contain leading zeros.

 

Example 1:

Input: n = 1
Output: 5
Explanation: The good numbers of length 1 are "0", "2", "4", "6", "8".

Example 2:

Input: n = 4
Output: 400

Example 3:

Input: n = 50
Output: 564908303

 

Constraints:

• 1 <= n <= 1015

中文题目

我们称一个数字字符串是 好数字 当它满足（下标从 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 \frac{n+1}{2} \rfloor} \cdot 4^{\lfloor \frac{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)$。

统计信息

通过次数	提交次数	AC比率
4853	13377	36.3%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言