Cod sursa(job #2373895)

Utilizator alexghitaAlexandru Ghita alexghita Data 7 martie 2019 15:43:02
Problema Factorial Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <bits/stdc++.h>

using namespace std;

// Calculează numărul de zerouri al lui n!, adică de câte ori apare 5 în produs.
int get_num_of_zeros(int n) {
  int power = 5;
  int num_of_zeros = 0;

  while (power <= n) {
    num_of_zeros += n / power;
    power *= 5;
  }

  return num_of_zeros;
}

// Caută binar răspunsul N pentru o anumită valoare țintă (P).
void binary_search(int l, int r, int target) {
  if (l > r) {
    cout << "1";
    return;
  }

  int mid = (l + r) >> 1;
  int num_of_zeros = get_num_of_zeros(mid);

  if (num_of_zeros == target) {
    mid -= mid % 5;
    cout << mid;
  } else if (num_of_zeros < target) {
    binary_search(mid + 1, r, target);
  } else {
    binary_search(l, mid - 1, target);
  }
}

int main() {
  freopen("fact.in", "r", stdin);
  freopen("fact.out", "w", stdout);

  int P;

  cin >> P;

  binary_search(1, P * 5, P);
}