Cod sursa(job #1765724)

Utilizator ilie.danilaIlie Teodor Danila ilie.danila Data 26 septembrie 2016 22:32:47
Problema Factorial Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
//
// Created by Ilie Danila on 26/09/2016.
//

#include <fstream>
#include <math.h>

using namespace std;

int radical(int bigNumber, int smallNumber)
{
    int result = 0;

    while( bigNumber >= smallNumber)
    {
        bigNumber = bigNumber / smallNumber;
        result++;
    }

    return result;
}

int p;

int main()
{
    ifstream fin("fact.in");
    fin >> p;
    fin.close();

    // Basically the result should be 5 * p;
    int result = 5 * p;

    // Now let's see how many zeros this (5*p)! actually has.

    // First let's find the biggest 5^x that divides (5*p)!
    int x = radical(result, 5);

    // We know that 5^2 add 1 extra zero, 5^3 adds 2 extra zeros, 5^4 adds 3 and so on...
    // 5^1 adds 0 extra zeros
    int extraZeros = (x * (x - 1)) / 2;

    int tempSolution = p;

    while( tempSolution + extraZeros > p)
    {
        tempSolution--; // Basic number of zeros
        x = radical(tempSolution * 5, 5);
        extraZeros = (x * (x - 1)) / 2;
    }

    ofstream fout("fact.out");
    if (tempSolution + extraZeros == p)
    {
        fout << tempSolution * 5 << "\n";
    }
    else
        fout << "-1\n";

    fout.close();

    return 0;
}