Medium

题目描述

如果数字字符串在偶数索引（从0开始）的数字是偶数，在奇数索引的数字是质数（2、3、5或7），那么这个数字字符串就是好的。

例如，“2582"是好的，因为偶数位置的数字（2和8）是偶数，奇数位置的数字（5和2）是质数。然而，“3245"不是好的，因为3在偶数索引位置但不是偶数。

给定一个整数 n，返回长度为 n 的好数字字符串的总数。由于答案可能很大，请返回结果对 10^9 + 7 取模的值。

数字字符串是由数字 0 到 9 组成的字符串，可以包含前导零。

示例 1：

输入：n = 1
输出：5
解释：长度为1的好数字是"0"、"2"、"4"、"6"、"8"。

示例 2：

输入：n = 4
输出：400

示例 3：

输入：n = 50
输出：564908303

约束条件：

  • 1 <= n <= 10^15

提示：

  • 是否有公式可以用来计算所有好数字的数量？
  • 如果我们查看 n 的二进制位，指数运算可以非常快速地完成。

解题思路

这是一个数学问题，需要用到快速幂算法。

分析：

  1. 偶数位置（0, 2, 4, …）可以放置偶数数字：0, 2, 4, 6, 8，共5个选择
  2. 奇数位置（1, 3, 5, …）可以放置质数数字：2, 3, 5, 7，共4个选择

关键观察：

  • 对于长度为 n 的字符串：
    • 偶数位置有 ⌈n/2⌉ 个（当 n 为奇数时多一个）
    • 奇数位置有 ⌊n/2⌋ 个
  • 总的好数字数量 = 5^(偶数位个数) × 4^(奇数位个数)

算法步骤：

  1. 计算偶数位和奇数位的个数
  2. 使用快速幂计算 5^偶数位个数 和 4^奇数位个数
  3. 两者相乘并取模

快速幂实现： 由于指数可能很大（n 最大 10^15），直接计算会超时，需要使用快速幂算法，时间复杂度 O(log n)。

这是推荐解法，时间复杂度最优。

代码实现

class Solution {
private:
    const int MOD = 1e9 + 7;
    
    long long fastPow(long long base, long long exp) {
        long long result = 1;
        while (exp > 0) {
            if (exp & 1) {
                result = (result * base) % MOD;
            }
            base = (base * base) % MOD;
            exp >>= 1;
        }
        return result;
    }
    
public:
    int countGoodNumbers(long long n) {
        long long evenCount = (n + 1) / 2;  // 偶数位个数
        long long oddCount = n / 2;         // 奇数位个数
        
        long long evenChoices = fastPow(5, evenCount);
        long long oddChoices = fastPow(4, oddCount);
        
        return (evenChoices * oddChoices) % MOD;
    }
};

class Solution:
    def countGoodNumbers(self, n: int) -> int:
        MOD = 10**9 + 7
        
        def fastPow(base, exp):
            result = 1
            while exp > 0:
                if exp & 1:
                    result = (result * base) % MOD
                base = (base * base) % MOD
                exp >>= 1
            return result
        
        evenCount = (n + 1) // 2  # 偶数位个数
        oddCount = n // 2         # 奇数位个数
        
        evenChoices = fastPow(5, evenCount)
        oddChoices = fastPow(4, oddCount)
        
        return (evenChoices * oddChoices) % MOD

public class Solution {
    private const int MOD = 1000000007;
    
    private long FastPow(long baseNum, long exp) {
        long result = 1;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result = (result * baseNum) % MOD;
            }
            baseNum = (baseNum * baseNum) % MOD;
            exp >>= 1;
        }
        return result;
    }
    
    public int CountGoodNumbers(long n) {
        long evenCount = (n + 1) / 2;  // 偶数位个数
        long oddCount = n / 2;         // 奇数位个数
        
        long evenChoices = FastPow(5, evenCount);
        long oddChoices = FastPow(4, oddCount);
        
        return (int)((evenChoices * oddChoices) % MOD);
    }
}

var countGoodNumbers = function(n) {
    const MOD = 1e9 + 7;
    
    function fastPow(base, exp) {
        let result = 1;
        while (exp > 0) {
            if (exp & 1) {
                result = (result * base) % MOD;
            }
            base = (base * base) % MOD;
            exp = Math.floor(exp / 2);
        }
        return result;
    }
    
    const evenCount = Math.floor((n + 1) / 2);  // 偶数位个数
    const oddCount = Math.floor(n / 2);         // 奇数位个数
    
    const evenChoices = fastPow(5, evenCount);
    const oddChoices = fastPow(4, oddCount);
    
    return (evenChoices * oddChoices) % MOD;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(log n)快速幂算法的时间复杂度
空间复杂度O(1)只使用常数额外空间

相关题目