解法一、迴圈

🔹 優化

Ofast 優化 :
#pragma GCC optimize("Ofast")
(-Ofast = -O3 + -ffast-math + 一些額外 aggressive 的最佳化)

輸出入優化 :
getchar_unlocked()、putchar_unlocked()

計算優化 :
用 n & 1 判斷奇偶數
用 n >>= 1 除以 2

當 a 是奇數時 a = a*3 + 1
那麼下一個 a 一定是偶數
因此可以一起處理 a = (a*3 + 1) >> 1

(因為測資 a > 2 否則需要對 1 做特判)

✅ 完整代碼

評分結果(參考) ： AC (0.2s, 320KB)

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")

bool readLL(long long &x){
    int c = getchar_unlocked();
    if(c == EOF) return false;
    while(c <= ' '){ 
        c = getchar_unlocked();
        if (c == EOF) return false;
    }

    x = 0;
    for(; c>='0' && c<='9'; c=getchar_unlocked())
        x = x*10 + (c-'0');

    return true;
}

void writeLL(long long x, char endc = '\n') {
    static char buf[32];
    int p = 0;
    if(x == 0) buf[p++] = '0';
    else{
        while(x > 0){
            buf[p++] = '0' + (x%10);
            x /= 10;
        }
    }
    while(p--) putchar_unlocked(buf[p]);
    putchar_unlocked(endc);
}

int main(){
    long long a, cnt;
    while(readLL(a)){
        cnt = 0;
        while(a != 4){
            if (a & 1){
                a = (a*3 + 1) >> 1;
                cnt += 2;
            }
            else{
                a >>= 1;
                cnt += 1;
            }
        }
        writeLL(cnt);
    }
    
    return 0;
}

解法二、遞迴

根據題目構造遞迴式 :

$f(x) = \left\{\begin{matrix} x/2\;\;\; & \text{if}\;x = 2k,\;\;\;\;\;\;\; k \in \mathbb{Z} \\ 3x + 1 & \text{if}\;x = 2k+1,\; k \in \mathbb{Z} \end{matrix}\right.$

然後別忘了優化

✅ 完整代碼

評分結果(參考) ： AC (0.2s, 328KB)

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")

bool readLL(long long &x){
    int c = getchar_unlocked();
    if(c == EOF) return false;
    while(c <= ' '){ 
        c = getchar_unlocked();
        if (c == EOF) return false;
    }

    x = 0;
    for(; c>='0' && c<='9'; c=getchar_unlocked())
        x = x * 10 + (c-'0');

    return true;
}

void writeLL(long long x, char endc = '\n') {
    static char buf[32];
    int p = 0;
    if(x == 0) buf[p++] = '0';
    else{
        while(x > 0){
            buf[p++] = '0' + (x%10);
            x /= 10;
        }
    }
    while(p--) putchar_unlocked(buf[p]);
    putchar_unlocked(endc);
}

long long f(long long a){
    if(a == 4) return 0;
    
    if(a & 1) return 2 + f((a*3 + 1) >> 1);
    else return 1 + f(a >> 1);
}

int main(){
    long long a;
    while(readLL(a)){
        writeLL(f(a));
    }
    
    return 0;
}