http://www.spoj.pl/problems/FACVSPOW/
Hi guys,
I'm trying to solve this problem but I'm getting TLE.
Basically, the problem wants to know when n! > (a ^ n) for a given (a <=
1000 000).
My basic idea was to pre-calculate all values n! for n <= e * 1000000
using log.
Then use binary search in the range [2 * a, (e * a)] to discover when n! >
a ^ n
Anyone have any ideas?
Wladimir Araujo Tavares
*Federal University of Ceará <http://lia.ufc.br/%7Ewladimir/>
Homepage <http://lia.ufc.br/%7Ewladimir/> |
Maratona<https://sites.google.com/site/quixadamaratona/>|
*
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <map>
#define MAX 2718281
using namespace std;
int i,t;
long double f[MAX];
long long int v[1000000];
long long int max;
long double g(long long int a,long long int n){
if(n==0) return 1;
else{
return n*log(a);
}
}
long long int menor(long long int a){
long long int inicio,meio,fim;
inicio = 2*a;
fim = (int)(M_E*a);
//printf("%lld\n",fim);
while(inicio < fim){
meio = (inicio+fim)/2;
//printf("%lld %lld\n",inicio,fim);
//printf("%lld\n",meio);
//printf("%llf %llf\n", f(meio),g(a,meio));
//system("PAUSE");
if( f[meio] > g(a,meio) ){
fim = meio;
}else{
inicio = meio+1;
}
}
return inicio;
}
int compara(const void *a,const void *b){
return *(int*)a - *(int*)b;
}
int main(){
long long int max;
//printf("%d\n",MAX);
scanf("%d",&t);
max = 0LL;
for(i=0;i<t;i++){
scanf("%lld",&v[i]);
if(v[i]>max) max = v[i];
}
f[0] = log(1);
for(i=1;i<M_E*max;i++)
f[i] = f[i-1] + log(i);
for(i=0;i<t;i++)
printf("%lld\n",menor(v[i]));
system("PAUSE");
}
