HDU 5167：Fibonacci——記憶化搜索判斷乘積分解

題目描述

判斷給定 n (≤ 1e9) 是否可表示為若干斐波那契數（F₁=1,F₂=1,F₃=2...）的乘積。多測試用例。

觀察

• 1e9 以內斐波那契數僅 44 個
• 遞歸嘗試除以每個 ≤ n 的斐波那契數，記憶化結果

C++ 實現

#include <cstdio>
#include <map>
using namespace std;
const int LIM = 1e9;
long long fib[50];
map memo; // 1:可分解, -1:不可, 0:未訪問

void init() {
    fib[1]=fib[2]=1;
    for(int i=3;;++i) {
        fib[i]=fib[i-1]+fib[i-2];
        if(fib[i]>LIM) break;
    }
}

bool dfs(int n) {
    if(memo.count(n)) return memo[n]==1;
    for(int i=3; fib[i]<=n; ++i)
        if(n % fib[i] == 0 && dfs(n/fib[i]))
            return memo[n]=1, true;
    return memo[n]=-1, false;
}

int main() {
    init(); memo[0]=memo[1]=1;
    int T; scanf("%d",&T);
    while(T--) {
        int n; scanf("%d",&n);
        puts(dfs(n) ? "Yes" : "No");
    }
    return 0;
}

複雜度

• 狀態數 ≤ 不同查詢 n 的因數組合，實際極少
• 每狀態嘗試 ≤ 44 次除法