My Weblog

Blog about programming and math

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

December 10, 2010 - Posted by | Programming

2 Comments »

  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


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: