2.1枚舉介紹

• 枚舉就是將所有答案的可能都跑過一次
• 若有時候答案的可能樹太多，會導致超時，在這個單元中，就要學習如何以合理的時間複雜度找到答案

枚舉簡單題目

給定一個數字$n(1\leq n\leq 10^3)$問可以湊成幾對$a, b$買足$a\times b = n$?

• 很直觀的做法，可以直接用$O(n^2)$的時間複雜度來完成

  #include<iostream>
  using namespace std;
  int main()
  {
      int n;
      cin >> n;
      int ans = 0;
      for(int i = 1; i <= n; i++) {
          for(int j = 1; j <= n; j++) {
             if(i * j == n) {
                  ans++;
             }
          }
      }
      cout << ans << endl;
      return 0;
  }
  

• 現在更改題目，將$n$的範圍改成$1\leq n\leq 10^5$，再去跑這個程式碼時，會發現程式遲遲跑不出結果來，因為很明顯地，$O(n^2)$會超時
• 現在我們會有幾種想法
  1. 以這個$n$的大小，必須要用$O(n)$的時間複雜度才可能完成
  2. $a\times b = n$可以轉換成$a=\frac{n}{b}$
• 用以上這兩種想法，相信你就可以想出如何使用$O(n)$解出這題了
• 只需要枚舉$n$並看看$n\\ b$使否整除即可