题目：统计好数字的数目
我们称一个数字字符串是好数字当它满足（下标从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
语言:C++
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;    }
};
语言:C++
class Solution {
private:
using LL = long long;
int MOD = 1e9 + 7;
public:
int countGoodNumbers(LL n) {
LL odd = n / 2;
LL even = n - odd;
return ((LL)quickMulti(4, odd) * quickMulti(5, even)) % MOD;
}
int quickMulti(LL a, LL b) {
LL cur = a, ans = 1;
while (b) {
if (b & 1) ans = ans * cur % MOD;
cur = cur * cur % MOD;
b >>= 1;
}
return ans;
}
};
语言:Python
class Solution:
def countGoodNumbers(self, n: int) -> int:
mod =10**9+7
# 快速幂求出 x^y % mod
def quickmul(x: int, y: int) -> int:
ret, mul =1, x
while y >0:
if y %2==1:
ret = ret * mul % mod
mul = mul * mul % mod
y //=2
return ret
return quickmul(5, (n +1) //2) * quickmul(4, n //2) % mod
语言:java
字符串长度统计static int count = 0;
public static int countGoodNumbers(long n) {
dfs(0,(int)n,new StringBuilder());
return count;
}
public static void dfs(int i, int n, StringBuilder sb){ if(i>=n){
String s =sb.toString();
for (int j = 0; j < n; j++) {
int a = s.charAt(j)-'0';
if(j%2==0){
if( a % 2 !=0){
break;
}
}else{
if(a!=2 && a!=3 && a!=7 && a!=5){
break;
}
}
if(j==n-1){
count++;
}
}
}else{
int N=10;
for (int j = 0; j < N; j++) {
StringBuilder ss=new StringBuilder(sb);
ss.append((char)('0'+j));
dfs(i+1,n,ss);
}
}
}
语言:java
public int countGoodNumbers(long n) {
int N=(int)Math.pow(10,9)+7;
//如果是奇数，还得乘个5
int cheng=1;
if(n%2==1){
cheng=5;
//n变为偶数
n-=1;
}
//n中有多少个偶数
long o=n/2;
// 4*5 的偶数次方
long a = myPow(20,o,N);
long ans = a * cheng;
return (int)(ans%N);
}
//快速幂 (记得要取余N，不只是结果取余，每次乘机也要取余) public long myPow(long x, long n,int N) {
if(n==0){
return1;
}
long m=n;
long sum=1;
while(m!=0){
if((m&1)==1){
sum*=x;
sum%=N;
}
x*=x;
x%=N;
m>>=1;
}
return sum;
}
语言:go
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
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。