HDU 3784 Collatz 猜想（3n+1）序列去重

HDU 3784 - Collatz 序列去重：標記中間值過濾輸入數字

對每個輸入數字 x，生成 Collatz 序列（偶數/2，奇數×3+1/2）直到 1。若輸入集合中某數字出現在其他數字的序列中，則輸出時過濾掉。剩餘數字按輸入逆序輸出。

算法

1. 讀入所有輸入數字到數組 a[]
2. 對每個 a[i]，生成其 Collatz 序列，將遇到的 ≤1000 的值標記在 vis[] 中
3. 逆序遍歷 a[]，若 !vis[a[i]] 則加入結果
4. 輸出結果

代碼

int a[3000005]; bool vis[3000005];
int main() {
    int n;
    while (scanf("%d", &n), n) {
        for (int i=0; i res;
        for (int i=n-1; i>=0; --i)
            if (!vis[a[i]]) res.push_back(a[i]);
        for (int i=0; i

關鍵點

只標記 ≤1000 的中間值，因輸入數字可能大但中間值收斂快
逆序輸出保證「後出現的優先保留」
Collatz 猜想未證但驗證至極大數均收斂，題目隱含此前提