這題對 python 來說，最大的性能瓶頸不是你的算法，而是 I/O 速度

可以說這題基本上就是考你怎麼優化 I/O 的

先講算法

根據題目提供的指示，最大的一組測資有 5*10^6 筆，每個數字你都要重新算嗎?

顯然不理智，所以請建表

事實上在 int 範圍內，2 的乘冪只有 31 個 (0 <= n < 2^32)，絕大部分的數字都不是 2 的乘冪

最後記得用 set 或 dict 這類建哈希表的資料結構保存所有數字，讓查找速度變成 O(1)

如果不建表，你是穩吃 TLE 的，試都不用試

什麼是 I/O 

I/O 優化可以往幾個方面著手

先說什麼是 I/O 

I/O 就是「輸入」與「輸出」，你每次執行一次 input() 或 print()，都算做是一次 I/O。

程式在運行時，處理輸入輸出時的時間開銷通常都會比較大一些，雖然現代的電腦已經可以壓到很低了，但面對這題這麼龐大的資數量，再小的開銷也會像蝴蝶效應一樣變得很龐大

既然 I/O 的開銷可能很大，那減少 I/O 不就好了嗎？

是的，這就是第一個解決方式：減少 I/O 的次數

但怎麼減少?

輸出

這個比較簡單，先講

你可以先把算出來的答案暫時先存起來，看你是要存成 str 還是 list 都可以，你開心就好，

最後再用 print() 一口氣全部輸出，讓你的程式從頭到尾就只執行一次 print()，而不是每次循環就 print() 一次。

像這樣

nums = set()    # 你建的表，這部分請自己做
result = []     # 答案放這，先不急著輸出

while True:
    try:
        n = int(input())
        result.append('Yes' if n in nums else 'No')

    except EOFError:
        break

print('\n'.join(result))    # 最後才一口氣輸出答案

# 你也可以寫下面這樣，但這樣做的開銷會比較大一些
# print(*result, sep='\n')

這樣我們就減少很大一部分的 I/O 開銷

從原本的 5*10^6 次 print() 變成 1 次，效率就高起來了

代價是你的程式占用的記憶體會比較大，以空間換時間是加速程式執行效率常用的策略 (建表本身也是以空間換時間)。

一些題目只需要做到這程度就可以避免 TLE 了

但在這題的話這樣還不夠

避免 try...except 語句

如果你處理輸入一直都是用 try...except 把程式包起來，那效率肯定是不怎麼樣

Why？

因為 try 這個東西開銷也很大，程式每次執行被 try 包起來的語句時，總是要在主要邏輯外，額外檢查有沒有錯誤，是什麼錯誤

try 用得越多，效率就會越差

當我們追求效率時，應該盡可能避免使用 try

try 只用在比起效率，你更重視其他方面的東西時才會使用

但這題又要讀到 EOF，怎麼辦? 要怎麼讓程式讀到 EOF 就停?

這時候要端出 sys 了。

通常來說，大部分題目沒必要刻意用他都能過，但這題還真的非他不可

使用 sys.stdin (1)

要使用 sys ，你得先執行 import sys

裡面包含很多奇怪的功能，都和 python 底層的運作原理有關，非常不直覺，一點都不 pythonic

這邊我們要用到 sys.stdin 標準輸入流，取代 input()

在 python 底層一點的運作原理中， input() 實際上就是先調用了 sys.stdin 輸入資料

每次輸入到換行符 \n 為止，最後回傳一個不包含換行符 \n 的字串

input() 實際上做的事情比你想像中的還要多，所以 input() 開銷大

你可以這樣使用 sys.stdin 

import sys

for num in sys.stdin:
    # 你的主要邏輯放這

這樣寫的效果就相當於

while True:
    try:
        num = input()
        # 你的主邏輯放這

    except EOFError:
        break

    # 或放這，你爽就好

這就是避免使用 try 的方法，這個寫法可以幫助我們自動讀到 EOF 為止，不需要再使用 try 包起來，從而避免 try 造成的額外開銷。

但這依然還有細節要注意

平時我們使用 input() 時，都是隨便拿到資料就直接用，通常不需要額外處理，因為 input() 已經幫你處理好格式了。

但 sys.stdin 可沒有這功能，它不處理格式，用上面的方式讀資料的話，每一列資料的結尾都會多一個換行符 \n

我們不需要這個，所以處理前記得要先 rstrip() 掉

當然，這題你也可以不理它，直接用 int() 包起來就好，因為 int() 本身就自帶格式分析的功能，會自己忽略 \n

補充說明：

這也是最常用的作法，在競程和各大 online judge 中很多人會用，但在實際的專案中......就少見很多了，因為 python 的優勢是可讀性、開發快，而不是執行效率，在現實中的專案中，如果遇到性能瓶頸，如果你追求的是執行效率，應該選擇改用其他速度更快的語言重寫，而不是糾結在這。

使用 sys.stdin (2)

99% 的題目都只需要用到上面的方法就可以 AC

但如果上面的方法就可以 AC 這題的話，那我也不需要再寫這段了

sys.stdin 除了上面的用法外，還有很多小功能可以使用，這邊列舉一些我常用的

sys.stdin.readline ：

逐行輸入，和 input() 差不多，區別在於 這個會保留換行符 \n，不需要的話記得 rstrip()

sys.stdin.read：

一口氣讀入所有資料，對，我是說所有，會返回一個長長長的字串。

以這題來說的話，大概是這個格式 12\n13\n14\n

sys.stdin.readlines：

(注意結尾有 s)

一口氣讀入所有資料，然後把所有資料根據換行符的位置轉換成 list。

當然，每個元素的最後面都還是會自帶 \n，大概是這種格式 ["12\n", "13\n", "14\n"]

這邊我們需要的是 sys.stdin.read 或 sys.stdin.readlines，一口氣讀入所有資料。

為什麼要這樣做？

因為上面用的 for num in sys.stdin 的作法，本質上只是避免 input() 的格式處理開銷和 try...except 造成的負擔，但實際上還是調用了 5*10^6 次輸入。

雖然它已經超級快了，但在這題還是不夠快，所以我們要像前面減少 print() 次數一樣，減少調用 input() 的次數

借助這兩個方法，我們就可以把 5*10^6 次輸入變成一次輸入！

但要怎麼用呢?

sys.stdin.readlines 比較簡單，上面的改一改就能直接用

import sys

for num in sys.stdin.readlines():
    # 你的主要邏輯放這

夠簡單吧~

幾乎一模一樣，只需要在後面補上 readlines 就好

sys.stdin.read 稍微麻煩一點，但也不難，因為它就是一個字串

你直接對他 split() 就可以了，但記得是要根據換行符 \n 的位置 split()

import sys

for num in sys.stdin.read().split('\n'):
    # 你的主要邏輯放這

對 python 語法更熟悉的人可能會用另一個東西: splitlines()

import sys

for num in sys.stdin.read().splitlines():
    # 你的主要邏輯放這

本質上是差不多的

透過上面提到的這些方法，你已經可以將輸入、輸入的次數從 5*10^6 次壓到各 1 次就好，大幅降低 I/O 的成本。

這樣就可以 AC 這題了

使用 sys.stdout

既然 input() 本質上是調用了 sys.stdin，那 print() 是調用了什麼? 就是這個 sys.stdout

你可以使用 stdout 取代 print()

怎麼做呢?

這邊我們只需要用到 sys.stdout.write 這個方法即可，把這篇文最一開始提到的那段程式碼 (我直接複製貼過來)

nums = set()    # 你建的表，這部分請自己做
result = []     # 答案放這，先不急著輸出

while True:
  try:
      n = int(input())
      result.append('Yes' if n in nums else 'No')

  except EOFError:
        break

print('\n'.join(result))    # 最後才一口氣輸出答案

# 你也可以寫下面這樣，但這樣做的開銷會比較大一些
# print(*result, sep='\n')

直接把那個 print 原封不動的改成 sys.stdout.write ，然後在最後面補上 \n 就可以了

像這樣 sys.stdout.write('\n'.join(result) + '\n')

通常不需要用到這招，因為 print() 本身就已經優化很好了

但用這個確實可以再增加一點效率。

--

題外話：

其實真要說的話， sys.stdin 其實還能更快，和 bytes 有關，進入到非人類語言的境界，但不直覺，這題也沒有必要使用

I/O 優化的手段除了在競程中會用到外，

在現實中的專案，如果你要做多執行序並行計算的話也有機會用到

說人話就是我們在這寫的都是單線程程式，只有一顆 cpu 在那邊努力算數學

如果你要讓很多顆 cpu 一起幫忙算，那就會有 I/O 的問題要處理

很難寫就是了，我也不太會