Cod sursa(job #813187)

Utilizator sg_ratingStefan Alexandru sg_rating Data 15 noiembrie 2012 00:02:30
Problema Factorial Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <cstdio>

unsigned long long computeNumZeroDigits(unsigned long long n) {
    unsigned long long digits = 0;
    while (n >= 1) {
        n /= 5;
        digits += n;
    }
    return digits;
}

int main() {
    freopen("fact.in", "r", stdin);
    freopen("fact.out", "w", stdout);
    unsigned long long p;
    scanf("%llu", &p);
    if (p == 0) {
        printf("1");
        return 0;
    }
    unsigned long long left = 0;
    unsigned long long right = 1000000001;
    unsigned long long n;
    unsigned long long last_found = -1;
    do {
        n = (left + right) / 2;
        unsigned long long num_zero_digits = computeNumZeroDigits(n);
        if (num_zero_digits < p) {
            left = n + 1;
        }
        else if (num_zero_digits > p) {
            right = n - 1;
        }
        else {
            last_found = n;
            right = n - 1;
        }
        if (left > right) {
            break;
        }
    } while (true);
    printf("%llu", last_found);
    fclose(stdin);
    fclose(stdout);
    return 0;
}