## Project Euler 297

After long time i solved problem from project euler. The problem is Project Euler problem 297 . Although it took some time to figure out the solution. First i brute forced and tried to get pattern. The problem is Given f(k) is the Kth Fibonacci number : sum(1, f(k)) = sum(1, f(k-1)) + sum(1, f(k-2)) + f(k-2) - 1 for non fibonacci number a [f(k-1) < a < f(k)] sum(1, a) = sum(1, f(k-1)) + sum(1, a - f(k-1)) + (a - f(k-1))

#include<cstdio> #include<iostream> using namespace std; typedef long long ll; ll fib[90],sum[90]; ll lim=1; ll recur(ll n) { if(n<=2) return sum[n]; else { int t; for(int i=0;i<90;i++) { if (fib[i]<=n) t=i;} return sum[t]+n-fib[t]+recur(n-fib[t]); } } int main() { for(int i=0;i<17;i++) lim=lim*10; fib[0]=0,fib[1]=1,fib[2]=2; sum[0]=0,sum[1]=1,sum[2]=2; for(int i=3;i<90;i++) { fib[i]=fib[i-1]+fib[i-2]; sum[i]=sum[i-1]+sum[i-2]+fib[i-2]-1; } cout<<recur(lim-1)<<endl; }

Advertisements

No comments yet.

## Leave a Reply