week3-[循環嵌套]好數

題目描述

如果一個正整數 $x$ 只有最左邊一位不是 $0$，其余都是 $0$，那么稱其為好數。例如 $4000$ 和 $2$ 都是好數，但是 $120$ 不是。

給定正整數 $n$，在 $1$ 到 $n$ 間有多少個數是好數？又有多少個數能表示為兩個好數的和？

輸入格式

輸入共 $1$ 行 $1$ 個正整數 $n$。

輸出格式

輸出共 $2$ 行。

第 $1$ 行 $1$ 個整數表示有多少個數是好數。

第 $2$ 行 $1$ 個整數表示有多少個數能表示為兩個好數之和。

樣例 #1

樣例輸入 #1

15

樣例輸出 #1

10
14

提示

樣例解釋 $1$

$1,2,3,4,5,6,7,8,9,10$ 都是好數。

數據范圍

對于所有數據，$1\le n\le 10000$。

這題分兩部分：統計好數 和 統計能表示為兩個好數之和的數。

---

🔎 分析

1?? 什么是好數

• 定義：只有最左邊一位不是 0，其余都是 0。
• 也就是形式為 d * 10^k，其中 d=1~9，k ≥ 0。
• 例子：
  • 2 → 好數
  • 10 → 好數
  • 120 → 不是好數

方法：

• 對 1~n 遍歷：
  • 轉字符串檢查是否首位非零，其余都是零
  • 或者數學方法：判斷 x 是否能被其首位數字后的 10 的冪整除

---

2?? 統計能表示為兩個好數之和的數

• 先生成所有好數 good[] ≤ n
• 枚舉所有兩兩組合 good[i] + good[j] ≤ n → 計數
• 注意：不同組合得到相同的和只算一次 → 用布爾數組 ok[1..n] 標記

---

📝 C++ 實現

#include <bits/stdc++.h>
using namespace std;// 判斷一個數是否為好數
bool isGood(int x) {while (x % 10 == 0 && x > 0) x /= 10; // 去掉末尾0return x >= 1 && x <= 9;               // 去掉末尾0后是否在1~9
}int main() {int n;cin >> n;vector<int> good;for (int i = 1; i <= n; i++) {if (isGood(i)) good.push_back(i);}cout << good.size() << endl;vector<bool> can(n+1, false);for (int i = 0; i < good.size(); i++) {for (int j = i; j < good.size(); j++) {int sum = good[i] + good[j];if (sum <= n) can[sum] = true;}}int cnt = 0;for (int i = 1; i <= n; i++) if (can[i]) cnt++;cout << cnt << endl;return 0;
}c++