Cod sursa(job #1698685)

Utilizator mihaixdmihai iacov mihaixd Data 5 mai 2016 00:43:14
Problema Factorial Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>
#include <math.h>
using namespace std;

ifstream f("fact.in");
ofstream g("fact.out");
int suma(long int n,int maxP)
{
    int i,s=0;
    for(i=1;i<=maxP;i++)
        s += n/pow(5,i);
    return s;
}
int main()
{
    long int p,n;
    int maxP;
    f>>p; //numarul de zerouri
    int k;
    if(p == 0) g<<1;
    else{
        // zerouri oferite de (5^a - 1)! : 1-1 + 5-1 + 25-1 + 125-1 + ...5^a-1 = 1 + 5 + 25 +...+5^a - a
        // maxP : 1 + 5 + 25 + ... + 5^maxP = (5^(maxP+1) - 1)/(5-1) >= P, dar mai mic pt maxP-1
        maxP =ceil( log10(4*p + 1)/log10(5) -1);
        if( (p+maxP)*4 +1 >= pow(5,maxP+1)) maxP++;

        // p = n( 1/5 + 1/25 + 1/125 + ...+1/(5^maxP))
        // n = (4P*5^maxP)/(5^maxP - 1)
        n=5*ceil((4*p*pow(5,maxP-1)/(pow(5,maxP)-1)));
        while( suma(n,maxP) < p) n=n+5;
        if( suma(n,maxP) == p) g<<n;
        else g<<-1;
    }
    f.close();
    g.close();
    return 0;
}