## Project Euler 101

After long time again i started solving problems on Project Euler. I need to solve 20 more problems to go to level 2 (more than 150 + group) so i think i should go for it. Till now i have solved all the problems from first page , 17 remaining problem on page 2 and more than 30 problems on page 3 so currently i am trying to finish these back logs as my Govt job 🙂 me giving me enough time to pratice on topcoder and project euler.

This problem is related to Lagrange Interpolating Polynomial. May be you can look at wiki or mathworld before solving this problem. You just have to check the condition when OP(k,k+1) is equal to U_k+1 and you are done.

Here is my source code but use for better understanding.

#include<cstdio> #include<iostream> #include<vector> #include<iostream> using namespace std; vector<long long> V; long long generate(long long n) { //return n*n*n; return 1-n*(1-n*(1-n*(1-n*(1-n*(1-n*(1-n*(1-n*(1-n*(1-n))))))))); } long long lagran(long long n) { if(n==2) return 1LL;//constant long long sum=0LL; for(long long i=1LL;i<n;i++)//y1,y2,y3 { long long tmp_1=1LL,tmp_2=1LL; for(long long j=1;j<n;j++) { if(j==i) continue; tmp_1*=(n-j); tmp_2*=(i-j); } sum+=(tmp_1*V[i]/tmp_2);//assuming a perfect division } return sum; } int main() { //using lagrange interpolation long long sum=0; V.push_back(0LL); for(long long i=1;;i++) { V.push_back(generate(i)); if(lagran(i+1)==generate(i+1))//not bad polynomial break; else sum+=lagran(i+1); } cout<<sum<<endl; }

You can try this problem too.I solved it long time ago and just saw this problem mentioned on the forum.

No comments yet.

## Leave a Reply