Pagini recente » Cod sursa (job #1971989) | Cod sursa (job #2847173) | Cod sursa (job #2523304) | Cod sursa (job #1590284) | Cod sursa (job #2923021)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("fact.in");
ofstream fout("fact.out");
// first step: binary search
int computeNoZero(int nr){
int div = 5, sol = 0;
// div <= nr and nr < 10^8 => doesn't overflow
while(div <= nr){
sol += nr/div;
div *= 5;
}
return sol;
}
void binarySearch(int left, int right, int noZero, int &sol){
if(left <= right) {
int mid = left + (right - left)/2;
if(computeNoZero(mid) < noZero) {
binarySearch(mid + 1, right, noZero, sol);
}
else {
sol = mid;
binarySearch(left, mid - 1, noZero, sol);
}
}
}
int main() {
int P;
fin >> P;
int sol = -1;
if(P == 0){
sol = 1;
}
else {
binarySearch(1, 5*P, P, sol);
}
if(computeNoZero(sol) != P){
sol = -1;
}
fout<<sol;
}