From e5d733871eda3cb090b121b0d1a6c904fb6bb71c Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Sat, 12 Apr 2025 21:43:56 -0600 Subject: 1922. count good numbers --- count_good_numbers.c | 21 ++++++++++++++------- count_good_numbers.py | 19 +++++++++++++++---- 2 files changed, 29 insertions(+), 11 deletions(-) diff --git a/count_good_numbers.c b/count_good_numbers.c index 86432c4..639c723 100644 --- a/count_good_numbers.c +++ b/count_good_numbers.c @@ -12,17 +12,24 @@ * contain leading zeros. */ -const int MOD = 1e9 + 7; +static int mod = 1e9 + 7; -long long _pow(long long a, long long b) { - if (!b) - return 1; - return b % 2 ? a * _pow(a, b - 1) % MOD : _pow((a * a) % MOD, b / 2); +long long mod_exp(long long n, long long e) { + int res = 1; + n %= mod; + while (e > 0) { + if (e & 1) + res = res * n % mod; + e >>= 1; + n = n * n % mod; + } + return res; } int countGoodNumbers(long long n) { - long long odd = n / 2, even = n - odd; - return _pow(20, odd) * ((n % 2) ? 5 : 1) % MOD; + long long a = mod_exp(5, (n + 1) / 2); + long long b = mod_exp(4, n / 2); + return (int)((a * b) % mod); } int main() { diff --git a/count_good_numbers.py b/count_good_numbers.py index 93455c9..17243a6 100644 --- a/count_good_numbers.py +++ b/count_good_numbers.py @@ -13,15 +13,26 @@ contain leading zeros. class Solution(object): + mod = 10**9 + 7 + + def mod_exp(self, n, e): + res = 1 + n %= self.mod + while e > 0: + if e % 2 == 1: + res = (res * n) % self.mod + n = (n * n) % self.mod + e //= 2 + return res + def countGoodNumbers(self, n): """ :type n: int :rtype: int """ - cnt, x = 5 ** (n % 2), 20 - for _ in range(n // 2): - cnt = cnt * x % (10**9 + 7) - return cnt + a = self.mod_exp(5, (n + 1) // 2) + b = self.mod_exp(4, n // 2) + return (a * b) % self.mod if __name__ == "__main__": -- cgit v1.2.3