# My Weblog

## 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);
}
}
```

December 10, 2010 - Posted by | Programming

1. 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 | Reply

• 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 | Reply