统计好数字的数目

题目

https://leetcode.cn/problems/count-good-numbers/description/?envType=daily-question&envId=2025-04-13

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

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

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

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

实现

思路：乘法 + 快速幂

• 若 n 有 a 个偶数下标，每个下标可取 $[0,2,4,6,8]$ 5 种方案
• 若 n 有 b 个奇数下标，每个下标可取 $[2,3,5,7]$ 4 种方案 奇偶下标互相独立，根据乘法原理，答案为：$5^a\ast 4^b$ 注意：取模避免数值溢出
• 数字 n 的偶数位总数 ceil(n/2)，奇数位总数 floor(n/2)
• 快速幂参见👉快速幂Pow(x,n)

复杂度分析

• 时间复杂度：$O(logn)$
• 空间复杂度：$O(1)$

const MOD = 1_000_000_007n;
 
var countGoodNumbers = function(N) {
    const n = BigInt(N);
    return Number(pow(5n, (n + 1n) / 2n) * pow(4n, n / 2n) % MOD);
};
 
var pow = function(x, n) {
    let res = 1n;
    while (n) {
        if (n & 1n) {
            res = res * x % MOD;
        }
        x = x * x % MOD;
        n >>= 1n;
    }
    return res;
};