---

前言

這是刷算法題的第十一天，用到的語言是JS
題目：力扣 1922. 統計好數字的數目 (中等)

---

一、題目內容

我們稱一個數字字符串是 好數字 當它滿足（下標從 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¹⁵

二、解題方法

1. 暴力解法（會超時，此法不通）

1. 遍歷所有長度為n的數字字符串，判斷是否為好數字
2. 好數字的偶數下標處的數字為偶數且奇數下標處的數字為質數
3. 時間復雜度為O(n)，空間復雜度為O(1)
4. 由于n的范圍較大，暴力解法會超時，所以需要優化

代碼如下（實例）：

*** @param {number} n* @return {number}*/
var countGoodNumbers = function (n) {// 暴力解法let count = 0for(let i = 0; i.toString().length <= n; i++) {if (i.toString().length === n) {const si = i.toString() // 將數字轉換為字符串if (si.length > n) returnfor (let j = 0; j < si.length; j++) {let access = false  // 如果每一位數字都通過，則數量+1if (j % 2 === 0 && si[j] % 2 === 0) access = trueelse breakif( j > 10 ) {if (j % 2 && (si[j] % 2 === 2 || si[j] % 2 === 3 || si[j] % 2 === 5 || si[j] % 2 === 7)) access = trueelse break}if (access) count++}}}return count % (10 ** 9 + 7)
}// console.log(countGoodNumbers(1)) // 5 正確，也會打印，但也僅此而已
// console.log(countGoodNumbers(8)) // 40000000 正確，也會打印，但也僅此而已
// console.log(countGoodNumbers(9)) // 400000000正確，但是不會打印，可能直接超時了，或者打印時間非常慢

2. 快速冪運算

涉及到JS的 大數運算（關于大數運算的補充在下面有）

代碼如下（示例）：（使用了JS的 大數運算 ）

/*** @param {number} n* @return {number}*/
var countGoodNumbers = function (n) {// 此題無法使用暴力算法const MOD = BigInt(10 ** 9 + 7)// ai得到的邏輯思維：// 一個長度為n的字符串，偶數位置可以有02468五種選擇，奇數位置可以有2357四種選擇// 因此對其進行排列組合，可以得到好數字的個數一共是 (符合偶數位置的數字的個數 * 符合奇數位置的數字的個數)// 即 (5^evenFuhe) * (4^oddFuhe)const evenCount = BigInt(Math.ceil(n / 2)) // 偶數下標的數量const oddCount = BigInt(Math.floor(n / 2)) // 奇數下標的數量const count = (Fuhe(5n, evenCount, MOD) * Fuhe(4n, oddCount, MOD)) % MODreturn Number(count)
}// 快速冪運算的函數實現
const Fuhe = ( a, b, mod ) => {let ans = 1na = a % modwhile(b) {if( b & 1n) ans = (a * ans) % moda = (a * a) % modb >>= 1n}return ans
}

---

代碼：（下面的代碼沒有使用JS的 大數運算，會出現精準度問題）

/*** @param {number} n* @return {number}*/
var countGoodNumbers2 = function (n) {// 此題無法使用暴力算法const MOD = 10 ** 9 + 7// ai得到的邏輯思維：// 一個長度為n的字符串，偶數位置可以有02468五種選擇，奇數位置可以有2357四種選擇// 因此對其進行排列組合，可以得到好數字的個數一共是 (符合偶數位置的數字的個數 * 符合奇數位置的數字的個數)// 即 (5^evenFuhe) * (4^oddFuhe)const evenCount = Math.ceil(n / 2) // 偶數下標的數量const oddCount = Math.floor(n / 2) // 奇數下標的數量const count = (Fuhe(5, evenCount, MOD) * Fuhe(4, oddCount, MOD)) % MODreturn count
}
const Fuhe = ( a, b, mod ) => {let ans = 1a = a % modwhile(b) {if( b & 1) ans = (a * ans) % moda = (a * a) % modb >>= 1// b = Math.floor(b / 2) }return ans
}
console.log(countGoodNumbers2(50)) // 應該是564908303，而非564908313，但是打印的是564908313

3. 組合計數的思維

理解這個問題的數學思維需要我們從組合計數的角度出發，分析如何在特定的約束下選擇數字字符串。以下是分析的詳解：

邏輯分析

1. 字符串結構:

   • 我們需要生成的字符串長度為 ( n )。
   • 字符串的下標為 ( 0 ) 到 ( n-1 )。

2. 下標分類：

   • 偶數下標（如 0, 2, 4, …）和奇數下標（如 1, 3, 5, …）之間有不同的限制條件。
   • 偶數下標位置的數字必須是偶數。
   • 奇數下標位置的數字必須是質數。

3. 可能的選項：

   • 偶數的選擇: 偶數下標的位置可以選擇的數字有 0, 2, 4, 6, 8，共 5 種選擇。
   • 質數的選擇: 奇數下標的位置可以選擇的質數有 2, 3, 5, 7，共 4 種選擇。

組合計數的推導

1. 偶數下標的數量:

   • 在一個長度為 ( n ) 的字符串中，偶數下標的數量可以通過 evenCount = ?n / 2?計算得出。
     • 這表示當 ( n ) 為奇數時，偶數下標數量會比奇數下標數量多 1。

2. 奇數下標的數量:

   • 奇數下標的數量可以通過 oddCount = ? n / 2 ?計算得出。
     • 這表示當 ( n ) 為偶數時，偶數下標和奇數下標數量相等。

3. 總組合數的計算:

   • 對于每一個偶數下標，我們有 5 種選擇（偶數）。
   • 對于每一個奇數下標，我們有 4 種選擇（質數）。
   • 最終的好數字字符串數量可以通過將偶數下標的選擇和奇數下標的選擇相乘得到：
     goodNumbers = 5^evenCount × 4^oddCount

例子分析

假設 ( n = 4 )：

• 字符串有長度 4，下標為 0, 1, 2, 3。
• 偶數下標（0 和 2）: 2 個位置，每個位置可以選擇【0, 2, 4, 6, 8】中的任意一個，即 5 種選擇。
• 奇數下標（1 和 3）: 2 個位置，每個位置可以選擇【2, 3, 5, 7】中的任意一個，即 4 種選擇。

因此，字符串的組合數是：
goodNumbers = 5² × 4² = 25 × 16 = 400

思維小結論

通過這樣的數學推理，我們能夠清楚地理解在給定的條件下，為什么能夠將問題轉換為計算選項的排列組合。在面對其他類似的問題時，這種分解和組合的思維方式可以幫助我們有效解決復雜問題。

---

4.官方題解

4.1 方法一：快速冪

思路與算法：
對于偶數下標處的數字，它可以為 0,2,4,6,8 共計 5 種，而長度為 n 的數字字符串有 ? n+1 / 2 ? 個偶數下標，其中 ?x? 表示對 x 向下取整。

對于奇數下標處的數字，它可以為 2,3,5,7 共計 4 種，而長度為 n 的數字字符串有 ? n / 2 ? 個奇數下標。

因此長度為 n 的數字字符串中，好數字的總數即為：
5^? n+1 / 2 ?^ ? 4^? n / 2 ?^
在本題中，由于 n 的取值最大可以到 10¹⁵，如果通過普通的乘法運算直接求出上式中的冪，會超出時間限制，因此我們需要使用快速冪算法對冪的求值進行優化。

快速冪算法可以參考「50. Pow(x, n)」的官方題解。

代碼如下（示例）：

var countGoodNumbers = function(n) {const mod = 1000000007n;// 快速冪求出 x^y % modfunction quickmul(x, y) {let ret = 1n;let mul = x;while (y > 0) {if (y % 2n === 1n) {ret = (ret * mul) % mod;}mul = (mul * mul) % mod;y = y / 2n;}return ret;}return Number(quickmul(5n, BigInt(n + 1) / 2n) * quickmul(4n, BigInt(n) / 2n) % mod);
};作者：力扣官方題解
鏈接：https://leetcode.cn/problems/count-good-numbers/solutions/857968/tong-ji-hao-shu-zi-de-shu-mu-by-leetcode-53jj/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

復雜度分析：

時間復雜度：O(log n)。

空間復雜度：O(1)。

鏈接：力扣本題官方題解
來源：力扣（LeetCode）

三、快速冪運算

快速冪運算（Exponentiation by Squaring）

快速冪運算是一種高效計算 ( b^e ) 的算法，其中 ( b ) 是基數，( e ) 是指數。傳統的逐步乘法方法的時間復雜度為 ( O(e) )，而快速冪運算的時間復雜度為 ( O(\log e) )，因此在處理大數時特別有效。

基本思想

快速冪運算的基本思想是利用平方和乘法來減少乘法的次數。其主要依據是：

• 如果指數 ( e ) 為偶數，則 ( b^e = (b^{e/2})2 )
• 如果指數 ( e ) 為奇數，則 ( b^e = b \times b^{e-1} )

通過這種方式，可以在每次迭代中將指數減半，從而顯著降低計算時間。

算法實現（②③為非遞歸）

以下是使用 JavaScript 實現的快速冪運算的代碼：

① 遞歸運算

/**  不帶模數* 快速冪運算* @param {number} base - 基數* @param {number} exp - 指數* @returns {number} */
function quickPow(base, exp) {if (exp === 0) {return 1; // 任何數的零次方為 1}if (exp % 2 === 0) {const half = quickPow(base, exp / 2);return half * half;} else {return base * quickPow(base, exp - 1);}
}

② 普通 除模運算（不帶 模數 與 帶 模數）

/** 不帶模數* 快速冪運算* @param {number} a- 基數* @param {number} b- 指數* @returns {number} 計算結果 (a ^ b)*/
function quick (a, b) {let ans = 1while(b) { // 當指數存在的時候// 如果指數是奇數，則要先拉出來一個底數乘到最終結果上，其余步驟和偶數一樣操作// 如果指數是偶數，則要底數平方，指數除以2（如果是使用按位與運算，則使用 "b >>= 1"）b/2if(b % 2 === 1) ans *= aa *= ab = Math.floor(b / 2) // 注意一定要使用Math.floor()，否則會出現小數點，導致結束循環}return ans
}
console.log(quick(2, 7)) // 128/**  帶模數* 快速冪運算* @param {number} base - 基數* @param {number} exp - 指數* @param {number} mod - 模數* @returns {number} 計算結果 (base^exp) % mod*/
const modExp = (base, exp, mod) => {let result = 1; // 初始化結果為 1base = base % mod; // 將基數在模數下取值while (exp > 0) {// 如果 exp 為奇數，將當前的 base 乘入結果if (exp % 2 === 1)  result = (result * base) % mod;// 將 base 平方base = (base * base) % mod;// exp 右移，相當于整除 2exp = Math.floor(exp / 2);}return result; // 返回最終結果
}

③ 按位與運算

/** 不帶模數* 快速冪運算* @param {number} a- 基數* @param {number} b- 指數* @returns {number} 計算結果 (a ^ b)*
function quick2 (a, b) {let ans = 1while(b) { // 當指數存在的時候// 如果指數是奇數，則要先拉出來一個底數乘到最終結果上，其余步驟和偶數一樣操作// 如果指數是偶數，則要底數平方，指數除以2（如果是使用按位與運算，則使用 "b >>= 1"）b/2if(b & 1) ans *= aa *= ab >>= 1 // b右移一位}return ans
}
console.log(quick2(2, 8)) // 256

使用示例

快速冪運算可以用于很多應用場景，包括計算大數的冪、加密算法、以及任何需要快速計算大數時。

示例代碼

const MOD = 10 ** 9 + 7; // 定義模數console.log(modExp(2, 10, MOD)); // 輸出: 1024
console.log(modExp(5, 3, MOD));  // 輸出: 125
console.log(modExp(3, 7, MOD));  // 輸出: 2187
console.log(modExp(10, 9, MOD)); // 輸出: 1000000000

復雜度分析

• 時間復雜度: ( O(log e) ) — 每次操作將指數減半。
• 空間復雜度: ( O(1) ) — 僅使用常量級額外空間。

小結論

快速冪運算是一個非常實用且高效的算法，廣泛應用于計算大數的冪以及各種算法中。了解并實現該算法可以顯著提高程序運行效率，特別是在處理與模數運算相關的問題時。

---

四、JS的大數運算

JavaScript 在處理數字時，其默認的數值類型是基于 IEEE 754 標準的雙精度浮點數。這個數值類型有一些限制，特別是在進行大數運算時。以下是 JavaScript 中大數運算的簡單介紹：

1. 數字精度限制

• 安全整數: JavaScript 支持的安全整數范圍是 (-2^{53} + 1) 到 (2^{53} - 1)（即 Number.MAX_SAFE_INTEGER 的值為 9007199254740991）。超出這個范圍的整數計算可能會出現精度丟失（例如， 9007199254740992 會變成 9007199254740992）。

• 浮點數問題: 由于浮點數的表示方式，某些小數（如 0.1 和 0.2 的和）可能無法精確表示。

2. 大數解決方案

由于上述限制，處理大數運算時，可以考慮以下幾種方案：

2.1. 使用 BigInt

從 ES2020 開始，JavaScript 引入了 BigInt 類型，用于表示任意大小的整數。你可以通過在數字后添加 “n” 來創建 BigInt：

const bigInt1 = BigInt(9007199254740992)
const bigInt2 = 12345678901234567890n // 后綴 "n" 表示 BigInt
const sum = bigInt1 + bigInt2         // 可以進行大數運算
console.log(sum)                       // 輸出: 12345678901234567892nconsole.log(Number(sum))  // 輸出: 12345678901234567892

2.2. 使用第三方庫

如果你需要支持比 BigInt 更廣泛的數值（比如更復雜的數學操作、浮點數等），可以使用大數運算庫，例如：

• Decimal.js: 支持任意精度的十進制運算，適合處理小數。
• Big.js: 提供了對大浮點數的高精度運算支持。
• bignumber.js: 可以處理比較大的數值以及高精度的浮點數運算。

使用示例（以 decimal.js 為例）：

const Decimal = require('decimal.js');const a = new Decimal(0.1);
const b = new Decimal(0.2);
const sum = a.plus(b); // 精確計算
console.log(sum.toString()); // 輸出: "0.3"

2.3. 總結

在 JavaScript 中，大數運算可以通過 BigInt 來實現任意大小的整數計算，或使用第三方庫來處理更復雜的場景（如浮點數和高精度計算）。在處理大數運算時，需要注意原生數值類型的限制，以確保計算的準確性。

2.4 補充：本題使用大數運算的例子

代碼如下：

/*** @param {number} n* @return {number}*/
var countGoodNumbers = function (n) {// 此題無法使用暴力算法const MOD = BigInt(10 ** 9 + 7)// ai得到的邏輯思維：// 一個長度為n的字符串，偶數位置可以有02468五種選擇，奇數位置可以有2357四種選擇// 因此對其進行排列組合，可以得到好數字的個數一共是 (符合偶數位置的數字的個數 * 符合奇數位置的數字的個數)// 即 (5^evenFuhe) * (4^oddFuhe)const evenCount = BigInt(Math.ceil(n / 2)) // 偶數下標的數量const oddCount = BigInt(Math.floor(n / 2)) // 奇數下標的數量const count = (Fuhe(5n, evenCount, MOD) * Fuhe(4n, oddCount, MOD)) % MODreturn Number(count)
}// 快速冪運算的函數實現
const Fuhe = ( a, b, mod ) => {let ans = 1na = a % modwhile(b) {if( b & 1n) ans = (a * ans) % moda = (a * a) % modb >>= 1n}return ans
}