## SPOJ Problem FUNFACT

This problem requires Stirling approximation and binary search.We search for lower bound value for (n+1) and this value will be upper bound for n. Source code for problem.

#include<cstdio> #include<iostream> #include<cmath> using namespace std; long long stirling(long long k) { double ret,n=k*1.0; ret=n*log(n)-n+0.5*log(2*M_PI*n)+(1.0/12.0/n)-(1.0/360.0/n/n/n)+(1.0/1260.0/n/n/n/n/n)-(1.0/1680/n/n/n/n/n/n/n); return ((long long)(ret*log10(M_E))+1LL); } int main() { long long t,n; for(scanf("%lld",&t);t>0;t--) { scanf("%lld",&n); n++;//search for lower bound for (n+1) long long lo=1LL,hi=1LL<<31,mid; while(lo<hi) { mid=(lo+hi)>>1; if(stirling(mid)<n) lo=mid+1; else hi=mid; } mid=(lo+hi)>>1; printf("%lld\n",mid-1); } }

Advertisements

could you please explain what’s :

ret=n*log(n)-n+0.5*log(2*M_PI*n)+(1.0/12.0/n)-(1.0/360.0/n/n/n)+(1.0/1260.0/n/n/n/n/n)-(1.0/1680/n/n/n/n/n/n/n)

Comment by rajesh | February 1, 2011 |

Dear Rajesh , its striling approximation with more precision.I already linked in the wiki article, kindly read it carefully. If you want to know about (1.0/1680/n/n/n/n/n/n/n) then its simply 1.0/(1680*n^7).

Comment by tiwari_mukesh | February 1, 2011 |