题意

有长度为n的木棍 最多能将其分成多少段 使得任意三段无法构成三角形

思路

很容易想到三角形性质是任意两边之和大于第三边 反之就是小于等于第三边 容易联想到斐波那契数列 某一项为前两项之和 里面都是符合题意的情况 由于要算多少个 我们求一个前缀和 计算需要多少长度才能分成该段 取最大值就是答案了 范围太大 要开ull 直接上java大数也行

代码

#include <bits/stdc++.h>

using namespace std;

#define ULL unsigned long long

ULL f[105];

int main(){
    ios::sync_with_stdio(0);

    f[1] = 1,f[2] = 1;

    for(int i = 3;i <= 91;i ++){
        f[i] = f[i - 1] + f[i - 2];
    }

    for(int i = 2;i <= 91;i ++){
        f[i] += f[i - 1];
    }

    int t;

    cin >> t;

    while(t --){
        ULL n;

        cin >> n;

        int res = 1;

        for(int i = 1;i <= 91;i ++){
            if(n >= f[i]){
                res = max(res,i);
            }else{
                break;
            }
        }

        cout << res << '\n';
    }
}