Cod sursa(job #1080975)

Utilizator impulseBagu Alexandru impulse Data 13 ianuarie 2014 02:22:23
Problema Factorial Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.86 kb
//
//  main.c
//  fact2
//
//  Created by Alexandru Bâgu on 1/12/14.
//  Copyright (c) 2014 Alexandru Bâgu. All rights reserved.
//

#include <stdio.h>

int fx(int n)
//fx(n) = n/5 + n/25 + n/125 + ...
{
    int k = 5, ct = 0;
    while(n >= k)
    {
        ct += n / k;
        k *= 5;
    }
    return ct;
}

int bin_sea(int p)
{
    int k = 1 << 30, i = 0, pMax = p * 5, zeros;
    while(k >>= 1)
    {
        if(i + k <= pMax)
        {
            zeros = fx(i + k);
            if(zeros == p) return i + k;
            else if(zeros < p) i += k;
        }
    }
    if(p == 0) return 1;
    return -1;
}

int main(int argc, const char * argv[])
{
    freopen("fact.in", "r", stdin);
    freopen("fact.out", "w", stdout);
    int p, q;
    scanf("%d", &p);
    q = bin_sea(p);
    while(fx(q) == p && q > 0) q--;
    if(q >= 0) q++;
    printf("%d", q);
    return 0;
}