[LeetCode] 每日一题 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 <= 10^15
解题思路
这题一读题就能看出思路其实非常直接：统计满足特定规则的数字字符串总数。
规则如下：
偶数下标（0, 2, 4...）必须是 偶数（可选数字：0, 2, 4, 6, 8，共5个）；
奇数下标（1, 3, 5...）必须是 质数（可选数字：2, 3, 5, 7，共4个）；
假设长度为 n，那么只要分别统计偶数位和奇数位上各自的组合数量，相乘即可。
于是，答案为：5^(偶数位个数) * 4^(奇数位个数)
也就是：
5^((n+1)/2) * 4^(n/2)
然而 n 最大可达 10^15，显然不能直接用 Math.pow 计算。因此，我们需要使用 快速幂算法 进行高效求解。
快速幂的核心思想是将指数 n 拆成若干个二进制位，用递归或迭代的方式，把乘法次数压缩到 O(log n)，极大提升效率。
我自己之前在
代码实现
class Solution {
int mod = 1000000007;
public int countGoodNumbers(long n) {
return (int)(pow(5, (n + 1) / 2) * pow(4, n / 2) % mod);
}
private long pow(int num, long n) {
long res = 1;
long mul = num;
while (n > 0) {
if (n % 2 != 0) {
res = res * mul % mod;
}
mul = mul * mul % mod;
n /= 2;
}
return res;
}
}复杂度分析
时间复杂度：
O(log n)
每次调用pow函数时最多进行log n次乘法，两个幂次各自调用一次空间复杂度：
O(1)
所有变量为基本数据类型，没有额外空间开销
🚀快速幂真的是处理大数乘法类题目的利器，在这种指数级爆炸的地方显得尤为重要！
总结
这道题本质上是数学题，思路简洁却非常典型，是快速幂算法的完美应用场景。虽然逻辑看起来简单，但背后的指数拆分、模运算都值得好好体会，是我在刷题中非常喜欢的一类题型。
如果你对快速幂还不熟，强烈建议了解一下快速幂的思路，这种思路在很多场景中都能派上大用场💡
希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。