How to find the number of digits in factorial of n of base b?

LightOJ 1045 – Digits of Factorial

Answer: 

1. At first Precalculate the logarithms of number 1 to n and add them all in an array, say, sum[n].
   sum[n]=log(1)+log(2)+....+log(n).
2. Now divide sum[n] by the log of b: log(b).
3. result= sum/log(b).
4. Add 1 to the result for final result.
5. Ans= result+1;
6. For any value of n you just need to divide sum[n] and you can get the result at O(1).

Solution:-

#include<bits/stdc++.h>

using namespace std;

long long i;

double dig[1000010];

main()

{

    long long n,cs=1;

    scanf("%lld",&n);

    for(i=1;i<=1000000;i++)

    {

        dig[i]=dig[i-1]+log(i);

    }

    while(n--)

    {

        long long  a,b,sum=0,res;

        long long ans;

        scanf("%lld%lld",&a,&b);

        res=(long long)(dig[a]/(dig[b]-dig[b-1]));

        ans=res+1;

        printf("Case %lld: %lld\n",cs++,ans);

    }

}