Cod sursa(job #3332665)

Utilizator TimofeiFilipTimofei Filip Emanuel TimofeiFilip Data 8 ianuarie 2026 14:08:19
Problema Factorial Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

unordered_map<ull, ull> um;

ull ApplyLegendre(ull factorial, ull prime) {
    ull power = prime;
    ull result = 0;
    while (power <= factorial) {
        result += factorial / power;
        power *= prime;
    }
    return result;
}

bool EnoughFactors(ull mid) {
    for (auto [prime, power] : um) {
        if (ApplyLegendre(mid, prime) < power)
            return false;
    }
    return true;
}

ull BinarySearch(ull number_of_zeros_at_end) {
    if (number_of_zeros_at_end == 0) return 1;

    um.clear();
    um[5] = number_of_zeros_at_end;

    ull left = 1, right = 5ULL * number_of_zeros_at_end;
    ull ans = 0;

    while (left <= right) {
        ull mid = left + (right - left) / 2;
        if (EnoughFactors(mid)) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    // Check if factorial has exactly P zeros
    if (ApplyLegendre(ans, 5) == number_of_zeros_at_end)
        return ans;
    else
        return -1;
}

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

    ull P;
    scanf("%llu", &P);

    ull result = BinarySearch(P);
    printf("%lld\n", result);

    return 0;
}