Cod sursa(job #543522)

Utilizator padreatiAurelian Tutuianu padreati Data 28 februarie 2011 10:29:51
Problema Factorial Scor 70
Compilator c Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <stdio.h>
#include <stdlib.h>

/*
 * Se rezolva numarand apartiiile factorilor 2 si 5 in factorial. 
 * Cu pixul si creionul.
 * 
 * Mai precis se cauta numai aparitiile lui 5. Caci 2 apare mult mai des, si daca sunt suficienti factori de 5,
 * cu siguranta sunt suficienti factori de 2. 
 * 
 * Cum anume cautam?
 * 
 * O idee care imi vine in minte este sa cautam cu binary search. Adica luam un numar oarecare, stim limitele, 
 * cat e minimum si cat e maximum (?!?).
 * Chiar daca nu am sti, putem cauta fara limita superioara.
 * 
 * Facem un guess oarecare. Apoi acel numar il impartim la 5, la 5*5, la 5*5*5 etc, pana cand puterea e mai mare decat acel numar.
 * Suma impartelilor este egala cu numarul factori 5.
 * O alta strategie de imaprtire este cu impartire mereu la 5, dar actualizare a deimpartitului. Ceva de genul:
 * 1. ghicim ceva = guess
 * 2. totalul = 0
 * 3. guess /=5;
 * 4. total += guess;
 * 5. revenim la 3. pana cand guess=0
 * 
 * Apoi folosind aceasta strategie micsoram intervalul de cautare pana la un numar.
 * Sa nu uitam sa suntam numarul la un multiplu de 5. adica ceva in genul nr.gasit -= nr.gasit%5
 * 
 */

long long fact_find(long long source) {
    long long t = 0;
    while (source) {
        source /= 5;
        t += source;
    }
    return t;
}

int main(void) {
    FILE *in = fopen("fact.in", "r");
    FILE *out = fopen("fact.out", "w");

    long long p;
    long long start = 0LL, stop = (1LL << 62);
    long long ret;

    fscanf(in, "%lld", &p);
    while ((stop - start) > 1) {
        long long mid = (start >> 1) + (stop >> 1);
        ret = fact_find(mid);
        if (ret >= p) {
            if (stop == mid)
                break;
            stop = mid;
        } else {
            if (start == mid)
                break;
            start = mid;
        }
    }

    if (ret == p) {
        fprintf(out, "%lld", stop);
        printf("%lld", stop);
    } else {
        fprintf(out, "-1\n");
        printf("-1\n");
    }

    return (EXIT_SUCCESS);
}