class Solution {
public:
int countGoodNumbers(long long n) {
}
};
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原站题解
cpp 解法, 执行用时: 0 ms, 内存消耗: 6 MB, 提交时间: 2023-09-06 23:52:59
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;
}
};
python3 解法, 执行用时: 44 ms, 内存消耗: 16.1 MB, 提交时间: 2023-09-06 23:52:15
class Solution:
''' 调用标准库
def countGoodNumbers(self, n: int) -> int:
MOD = 10 ** 9 + 7
a = pow(5, (n + 1) // 2, MOD)
b = pow(4, n // 2, MOD)
return (a * b) % MOD
'''
def countGoodNumbers(self, n: int) -> int:
MOD = 10 ** 9 + 7
def quick_mul(a: int, b: int) -> int:
res = 1
while b:
if b % 2 == 1:
res = res * a % MOD
a = a * a % MOD
b //= 2
return res
a = quick_mul(5, (n+1)//2)
b = quick_mul(4, n // 2)
return (a * b) % MOD
java 解法, 执行用时: 0 ms, 内存消耗: 37.8 MB, 提交时间: 2023-09-06 23:51:19
class Solution {
final int MOD = 1_000_000_007;
// 快速幂：注意 p 和 ans 都应该用 long 来计算，并且不应该分开计算快速幂！
public int quickmod(long p1, long n1, long p2, long n2) {
long ans = 1;
while(n1 > 0) {
if((n1&0x1) == 1) ans = (ans*p1)%MOD;
n1 >>= 1;
p1 = (p1*p1)%MOD;
}
while(n2 > 0) {
if((n2&0x1) == 1) ans = (ans*p2)%MOD;
n2 >>= 1;
p2 = (p2*p2)%MOD;
}
return (int)ans;
}
public int countGoodNumbers(long n) {
return quickmod(5, (n+1)/2, 4, n/2);
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-09-06 23:50:40
const mod int = 1e9 + 7
func countGoodNumbers(n int64) int {
return pow(5, (int(n)+1)/2) * pow(4, int(n)/2) % mod
}
func pow(x, n int) int {
res := 1
for ; n > 0; n >>= 1 {
if n&1 > 0 {
res = res * x % mod
}
x = x * x % mod
}
return res
}