Pagini recente » Cod sursa (job #441256) | Cod sursa (job #2956476) | Rating Radulescu Iulia Maria (raduiulia) | Rating neumark hermann (neumark) | Cod sursa (job #1652214)
#include <iostream>
#include <fstream>
#include <math.h>
using namespace std;
long factorial(int n) {
if (n == 0 || n ==1)
return 1;
else return n * factorial(n-1);
}
long smallestNo(int p) {
if (p == 0)
return 1;
long output = 0;
long multipliesFound = 0;
while (multipliesFound < p) {
output++;
if (output%625 == 0) {
multipliesFound += 5;
long temp = output/625;
long multiplies = 0;
while (temp%5 == 0) {
multiplies++;
temp = temp/5;
}
multipliesFound += multiplies;
} else if (output%125==0) multipliesFound += 4;
else if (output%25==0) multipliesFound += 3;
else if (output%5==0) multipliesFound += 2;
else multipliesFound += 1;
}
output *= 5;
if (multipliesFound > p) output = -1;
return output;
}
long long pow5(long exp) {
if (exp == 0) return 1;
else return 5 * pow5(exp-1);
}
long float log_5(long float x) {
return log(x) / log(5.0);
}
long trailingZeros(long n) {
long k = floor((float) log_5(n));
long acc = 5;
long output = 0;
for (int i = 1; i <= k; i++) {
output += floor((float) n/acc);
acc *= 5;
}
return output;
}
long factSearch(long p) {
int k = 1;
int sum = 1;
int prevSum = 1;
while (sum < p) {
long aux = sum;
sum = sum*5 + 1;
prevSum = aux;
k++;
}
if (sum == p) {
return pow5(k);
}
long long left = pow5(k-1), right = pow5(k);
long leftCount = trailingZeros(left), rightCount = trailingZeros(right);
while (left != right && left < right) {
long long middle = (left + right)/2;
long middleCount = trailingZeros(middle);
if (middle == left)
break;
if (middleCount == p)
return middle;
else if (middleCount < p) {
left = middle;
leftCount = middleCount;
} else {
right = middle;
rightCount = middleCount;
}
//cout<<left<<" "<<middle<<" "<<right<<endl;
}
if (leftCount != p)
return -1;
else return left;
}
int main(void) {
ifstream f("fact.in");
ofstream g("fact.out");
long p;
f>>p;
long output = factSearch(p);
g<<output;
return 0;
}