我们称一个数字字符串是 好数字 当它满足(下标从 0 开始)偶数 下标处的数字为 偶数 且 奇数 下标处的数字为 质数 (2,3,5 或 7)。
比方说,“2582” 是好数字,因为偶数下标处的数字(2 和 8)是偶数且奇数下标处的数字(5 和 2)为质数。 但 “3245” 不是 好数字,因为 3 在偶数下标处但不是偶数。
给你一个整数 n ,请你返回长度为 n 且为好数字的数字字符串 总数 。 由于答案可能会很大,请你将它对 10^9 + 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
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/count-good-numbers 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
int countGoodNumbers(long long n) {
long long odd = 0, even = 5, mod = 1e9+7;
bool flag = true;
while(--n)
{
if(flag)
odd = even*4%mod;
else
even = odd*5%mod;
flag = !flag;
}
return flag ? even : odd;
}
};
class Solution {
int mod = 1e9+7;
public:
int countGoodNumbers(long long n) {
long long y = (n+1)/2, x = n/2;
return (quickpow(4,x)*quickpow(5,y))%mod;
}
long long quickpow(long long a, long long x)
{
long long ans = 1, p = a;
while(x)
{
if(x&1)
{
ans = (ans*p)%mod;
}
p = (p*p)%mod;
x >>= 1;
}
return ans;
}
};
0 ms 5.9 MB C++
我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号(Michael阿明),一起加油、一起学习进步!