统计好数字的数目

5802. 统计好数字的数目

难度中等0

我们称一个数字字符串是 好数字 当它满足（下标从 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 <= 10^15

快速幂

计算20的n/2次幂，当n为偶数时，直接返回快速幂的结果，

如果n为奇数时，返回n/2次幂再乘以5

注意过程中的取余数计算！

class Solution {
    int MOD = (int) (1e9 + 7);
    int fastPower(long base, long power) {
        long result = 1;
        while (power > 0) {
            // 与运算代替求模
            if ((power & 1) == 1) {
                // 如果指数为奇数
                result = (result * base) % MOD; //把指数为奇数时分离出来的底数的一次幂计算上
            }
            // 右移代替除法
            power = power >> 1;
            base = (base * base) % MOD;
        }
        return (int) (result % MOD);
    }

    public int countGoodNumbers(long n) {
        if (n < 2) return 5;
        long power = n / 2;
        if (n % 2 == 0) {
            return fastPower(20L, power);
        } else {
            return (int)(((long)fastPower(20L, power)*5)% MOD);
        }
    }

}

赏

谢谢你请我吃糖果

微信