前言
好久没更新，1024水一题
正文
问题来源
本问题来自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
分析：
// 以为是水题，没想到超时了，哈哈
func countGoodNumbers(n int64) int {
mod := 1000000007
res := 1
for i := int64(0); i < n; i++ {
if i % 2 == 0 {
res *= 5
} else {
res *= 4
}
res %= mod
}
return res
}
快速幂
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
}
总结：
勤思考。
结语
不管怎么样好好加油。
