应该是矩阵+快速幂！

如果你问的是c++，我觉得优化的余地大概是把cin，cout换成scanf，printf，或者用模板在编译期完成计算。

但是这题显然要的是语言层面以外的优化，方法就是楼上说的矩阵快速幂，不过sicp上还有一个看起来很玄学的fibonacci算法，有兴趣可以看看:-)

楼上都是瞎说 这题其实考的是二分搜索hehe~

－－－－－－－－－－－－－－分割线－－－－－－－－
作为一个后端的nodejs新手 我决定用lua来实现给你看

local MAX = 48 -- 我是渣渣看错2^32 和10^32次了
local MIN = 1

local fib = {}
fib[1] = 1
fib[2] = 1
local i
for i=3, MAX do
    fib[i] = fib[i-1] + fib[i-2]
end

function fibFloor(x, max, min)
    if max == min+1 then
        return fib[min]
    else
        local mid = math.floor((max+min)/2)
        if (fib[mid] > x) then
            return fibFloor(x, mid, min)
        elseif (fib[mid] == x) then
            return fib[mid]
        else --if (fib[mid] < x) then
            return fibFloor(x, max, mid)
        end
    end
end

local n = io.read("*num")
for i=1, n do
    local x = io.read("*num")
    print(fibFloor(x, MAX, MIN))
end

看了楼下答案以后默默把MAX改成48...

c++14可以用constexpr + array + index_sequence直接生成fib数组,然后用lower_bound查询就行了。

#include <iostream>
#include <algorithm>
#include <array>
#include <type_traits>
#include <iterator>
#include <utility>

using namespace std;

constexpr uint64_t fib(size_t n) noexcept
{
  if (n < 2)
    return n;
  return fib(n - 1) + fib(n - 2);
}

template<typename F, size_t ... I>
constexpr auto make_array(F&& f, index_sequence<I...>) noexcept
{
  return array<result_of_t<F(size_t)>, sizeof...(I)>{
    f(I)...
  };
}

constexpr auto fib_arr = make_array(fib, make_index_sequence<94>());

int main()
{
  transform(istream_iterator<size_t>(cin), istream_iterator<size_t>(), ostream_iterator<size_t>(cout, "\r\n"), [&](auto v) {
    auto i = lower_bound(begin(fib_arr), end(fib_arr), v);
    return *i == v? v: i != fib_arr.begin()? *(i - 1): fib_arr.back();
  });

  return 0;
}

你用double干什么 double是浮点数
浮点运算慢啊

长的整型用long long

你用了int，而int最大只能到2^31 - 1
于是遇到些奇怪的m值的话，你算出来的fib会不断溢出成负数，然后死循环。

既然1 <= n <= 20000，你先把它们全算出来，硬编进源码里，要用时二分搜索就行了。
（楼上那些constexpr之类的高级技巧，本质上也是这样干，不过是由编译器在编译时代劳了……）

当然，再进阶一点的话，你可以用n = log(m * sqrt(5)) / log((sqrt(5) + 1) / 2)作为搜索起点。
因为fib(n) = round(((sqrt(5) + 1) / 2)^m / sqrt(5))

但其实上面这些都没甚么意义，因为fib(48) = 4,807,526,976，已经比2^32大了。
所以其实你只需要unsigned int[48]，根本不需要20000位。
你甚至可以硬编码出一堆if else来做这题……