蓝精灵之小饭写数字

题目：

蓝精灵之小饭写数字

题面：

有一个数列叫斐波那契数列，f(0)=0,f(1)=1,f(n)=f(n-1)+f(n-2)，小饭有支大力金刚笔，能写n位数字，她想知道，如果从f(1)开始写，她能写到第几个斐波那契数。。比如n=20，那么她能写。11235813213455891442。。。第13个斐波那契数。如果n=1亿，问小饭能写到第几个斐波那契数？

输入描述：

输入数据有多组。

输入一个整数n（0<n<1e8)。

输出描述：

输出答案。

输入样例：

20

输出样例：

13

题解

先用公式预处理出1e8个数需要多少个斐波那契数组成，然后求前缀和，二分查找合适的答案

#include 
    
     #include 
     
      typedef long long LL;LL ans[31000];int main() {    LL cnt = 0;    for(LL i = 1; cnt <= 100000000; i++) {        LL result = (long long)((double)i * log10(0.5 + 0.5 * sqrt(5)) - log10(sqrt(5))) + 1;        cnt += result;        ans[i] = cnt;    }    LL sum, ans1, ans2;    while(~scanf("%lld", &sum)) {        LL l = 0, r = 30935, mid;        while(r - l > 1) {            mid = (l + r) / 2;            if(ans[mid] <= sum && ans[mid + 1] >= sum) {                if(ans[mid] == sum) mid--;                break;            }            else if(ans[mid + 1] < sum) l = mid;            else r = mid;        }        printf("%lld\n", mid + 1);    }    return 0;}