LeetCode 1922. Count Good Numbers

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef long long LL;
const int MOD = 1000000007;
class Solution {
public:
    LL quickpow(LL x, LL n) {
        LL ans = 1;
        while (n) {
            if (n & 1) ans = ans * x % MOD;
            x = x * x % MOD;
            n /= 2;
        }
        return ans;
    }
    int countGoodNumbers(long long n) {
        return quickpow(5, (n + 1) / 2) * quickpow(4, n / 2) % MOD;
    }
};