17.6 log 複雜度：一直除以 2

\log 終於登場。10.1 當時說「先不用懂」，現在用一句話就能懂：

看它實戰：Codeforces 1475A - Odd Divisor。給 t \le 10^4 筆詢問，每筆一個 2 \le n \le 10^{14}，判斷 n 有沒有大於 1 的奇因數。

硬找奇因數是試除，太慢。換個角度想：什麼樣的數沒有大於 1 的奇因數？把 n 的因數 2 全部除光，剩下的一定是奇數——若剩下 1，表示 n 從頭到尾只由 2 組成（n 是 2 的次方），沒有奇因數；剩下大於 1，那個剩下的數本身就是奇因數。

「把 2 除光」正是「一直除以 2」——每筆詢問最多 \log_2 10^{14} \approx 47 次，10^4 筆總共不到 5 \times 10^5 次，快到可以忽略：

¶完整程式碼

#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        long long n;
        cin >> n;
        while (n % 2 == 0) n /= 2;         // 一直除以 2：最多 log n 次
        cout << (n > 1 ? "YES" : "NO") << '\n';
    }
    return 0;
}

執行結果（輸入題目範例 6 筆：2、3、4、5、998244353、1099511627776）：

NO
YES
NO
YES
YES
NO

現在回收 10.1 賣的關子：O(n \log n) 就是「掃一遍的工作做 \log n 層」。第十一單元的 sort 排 2 \times 10^5 筆資料，運算量約 2 \times 10^5 \times 18 \approx 4 \times 10^6——所以它才那麼快。\log 通常出現在「每一步把問題砍半」的地方：一直除以 2、每輪減半（17.5 你已經見過它的影子）、以及之後會學的二分搜尋（Level 1 先學怎麼用現成的工具，Level 2 才自己動手實作）。