Cod sursa(job #2906608)

Utilizator DobraVictorDobra Victor Ioan DobraVictor Data 26 mai 2022 19:17:52
Problema Factorial Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.21 kb
/*#include <fstream>
#include <climits>

struct factor {
    unsigned int val, pow;
};

int main() {
    std::ifstream fin("gfact.in");
    std::ofstream fout("gfact.out");

    unsigned long long p, q;
    factor factori[1000];
    unsigned long long factorC = 0;
    fin >> p >> q;

    unsigned long long cop = p;
    for(unsigned long long i = 2; cop > 1; ++i) {
        if(!(cop % i)) {
            cop /= i;
            factor& fac = factori[factorC++];
            fac.val = i;
            fac.pow = 1;

            while(!(cop % i)) {
                ++fac.pow;
                cop /= i;
            }
        }
    }
    
    unsigned long long start = 1, end = 10000000000;
    while(start != end) {
        unsigned long long mid = (start + end) >> 1;
        bool valid = true;

        for(unsigned long long i = 0; i < factorC && valid; ++i) {
            unsigned long long num = 0;

            for(unsigned long long pow = factori[i].val; pow <= mid; pow *= factori[i].val)
                num += mid / pow;
            
            valid = num >= q * factori[i].pow;
        }

        if(valid) {
            end = mid;
        } else {
            start = mid + 1;
        }
    }
    fout << start;

    fin.close();
    fout.close();

    return 0;
}*/

// fact
#include <fstream>
#include <climits>
 
int main() {
    std::ifstream fin("fact.in");
    std::ofstream fout("fact.out");
 
    unsigned long long p;
    fin >> p;
 
    unsigned long long start = 1, end = 10000000000;
 
    while(start != end) {
        unsigned long long mid = (start + end) >> 1, num = 0;
 
        for(unsigned long long pow = 5; pow <= mid; pow *= 5)
            num += mid / pow;
        
        if(num == p) {
            start = mid;
            break;
        } else if(num < p) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    start -= start % 5;
    if(!start) start = 1;

    unsigned long long num = 0;
    for(unsigned long long pow = 5; pow <= start; pow *= 5)
        num += start / pow;
    
    if(num != p) fout << "-1";
    else fout << start;
 
    fin.close();
    fout.close();
 
    return 0;
}