Cod sursa(job #2863784)

Utilizator robertbombasticRobert Beres robertbombastic Data 7 martie 2022 11:06:56
Problema Factorial Scor 85
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb

// C++ program tofind smallest number whose
// factorial contains at least n trailing
// zeroes.
#include<bits/stdc++.h>
using namespace std;

ifstream fin("fact.in");
ofstream fout("fact.out");

// Return true if number's factorial contains
// at least n trailing zero else false.
bool check(int p, int n)
{
    int temp = p, count = 0, f = 5;
    while (f <= temp)
    {
        count += temp/f;
        f = f*5;
    }
    return (count >= n);
}

// Return smallest number whose factorial
// contains at least n trailing zeroes
int findNum(int n)
{
    // If n equal to 1, return 5.
    // since 5! = 120.
    if (n==1)
        return 5;

    // Initalising low and high for binary
    // search.
    int low = 0;
    int high = 5*n;

    // Binary Search.
    while (low <high)
    {
        int mid = (low + high) >> 1;

        // Checking if mid's factorial contains
        // n trailing zeroes.
        if (check(mid, n))
            high = mid;
        else
            low = mid+1;
    }

    return low;
}

int main()
{
    int n;
    fin >> n;
    fout << findNum(n) << endl;
    return 0;
}