网站建设宣传素材,凡客家具是品牌吗,满城建设局官方网站,wordpress mylife文章目录1. 题目2. 解题1. 题目
我们称一个数字字符串是 好数字 当它满足#xff08;下标从 0 开始#xff09;偶数 下标处的数字为 偶数 且 奇数 下标处的数字为 质数 #xff08;2#xff0c;3#xff0c;5 或 7#xff09;。
比方说#xff0c;“2582” 是好数字下标从 0 开始偶数 下标处的数字为 偶数 且 奇数 下标处的数字为 质数 235 或 7。
比方说“2582” 是好数字因为偶数下标处的数字2 和 8是偶数且奇数下标处的数字5 和 2为质数。 但 “3245” 不是 好数字因为 3 在偶数下标处但不是偶数。
给你一个整数 n 请你返回长度为 n 且为好数字的数字字符串 总数 。 由于答案可能会很大请你将它对 10^9 7 取余后返回 。
一个 数字字符串 是每一位都由 0 到 9 组成的字符串且可能包含前导 0 。
示例 1
输入n 1
输出5
解释长度为 1 的好数字包括 02468 。示例 2
输入n 4
输出400示例 3
输入n 50
输出564908303提示
1 n 10^15来源力扣LeetCode 链接https://leetcode-cn.com/problems/count-good-numbers 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
数据范围很大直接做会吃T 超时的如下
class Solution {
public:int countGoodNumbers(long long n) {long long odd 0, even 5, mod 1e97;bool flag true;while(--n){if(flag)odd even*4%mod;elseeven odd*5%mod;flag !flag;}return flag ? even : odd;}
};可以发现这不就是求 4x5y4^x5^y4x5y 吗数据很大可以快速幂取模可以做掉 LeetCode 50. Pow(x, n)
class Solution {int mod 1e97;
public:int countGoodNumbers(long long n) {long long y (n1)/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(x1){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阿明一起加油、一起学习进步
