Cod sursa(job #3332663)

Utilizator TimofeiFilipTimofei Filip Emanuel TimofeiFilip Data 8 ianuarie 2026 14:07:07
Problema Factorial Scor 90
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(int number_of_zeros_at_end) {
    if (number_of_zeros_at_end > 0) {
        um[5] = number_of_zeros_at_end;
    }
    else {
        return 1;
    }

    ull left, right;
    ull ans = 0;

    left = 1;
    right = 5ULL * number_of_zeros_at_end;

    while (left <= right) {
        ull mid = (left + right) >> 1;
        if (EnoughFactors(mid)) {
            ans = mid;
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }
    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("%llu\n",result);
    return 0;
}