Нужна помощь в вопросе практики Codechef - найдите конечные нули в факториале

Question

Я работал над этим 24 часа, пытаясь оптимизировать его. Вопрос в том, как найти число конечных нулей в факториале от числа в диапазоне 10000000 и 10 миллионов тестовых случаев примерно за 8 секунд.

Код выглядит следующим образом:

#include<iostream>

using namespace std;

int count5(int a){
    int b=0;
    for(int i=a;i>0;i=i/5){
        if(i%15625==0){
            b=b+6;
            i=i/15625;
        }
        if(i%3125==0){
            b=b+5;
            i=i/3125;
        }
        if(i%625==0){
            b=b+4;
            i=i/625;
        }
        if(i%125==0){
            b=b+3;
            i=i/125;
        }
        if(i%25==0){
            b=b+2;
            i=i/25;
        }
        if(i%5==0){
            b++;
        }
        else
            break;

    }
    return b;
}
int main(){
    int l;
    int n=0;
    cin>>l; //no of test cases taken as input
    int *T = new int[l];

    for(int i=0;i<l;i++)
        cin>>T[i]; //nos taken as input for the same no of test cases


    for(int i=0;i<l;i++){
        n=0;
        for(int j=5;j<=T[i];j=j+5){
            n+=count5(j); //no of trailing zeroes calculted 
        }
        cout<<n<<endl; //no for each trialing zero printed
    }

    delete []T;


}   

Пожалуйста, помогите мне, предложив новый подход или предложив некоторые модификации этого.

Answer 1

Оптимальное решение выполняется за O(log N) время, где N - это число, для которого вы хотите найти нули.Используйте эту формулу:

Zeroes(N!) = N / 5 + N / 25 + N / 125 + ... + N / 5^k, пока деление не станет 0. Вы можете прочитать больше на wikipedia .

Так, например, в C это будет:

int Zeroes(int N)
{
    int ret = 0;
    while ( N )
    {
        ret += N / 5;
        N /= 5;
    }
    return ret;
}

Это будет работать в течение 8 секунд на достаточно быстром компьютере.Вероятно, вы можете ускорить его с помощью справочных таблиц, хотя я не уверен, сколько у вас памяти.

Вот еще одно предложение: не храните числа, они вам не нужны!Подсчитайте количество нулей для каждого числа, когда вы читаете его.

Если это для онлайн-судьи, то, по моему опыту, онлайн-судьи преувеличивают временные рамки для проблем, поэтому вам придется прибегать к уродливым взломам, даже если у вас есть правильный алгоритм.Один из таких уродливых способов - не использовать такие функции, как cin и scanf, а вместо этого использовать fread для одновременного чтения группы данных в массиве char, а затем анализировать эти данные (НЕ использовать sscanf или stringstreamsхотя) и получить цифры из него.Уродливо, но обычно намного быстрее.

Answer 2

Используйте следующую теорему:

Если p простое число, то высшее степень р, которая делит п! (п факториал) равен [n / p] + [n / p ^ 2] + [n / p ^ 3] + ... + [n / p ^ k], где k наибольшая степень p <= n, а [x] является неотъемлемой частью x. </p>

Ссылка: http://planetmath.org/encyclopedia/PrimePowerDividingAFactorial.html

Answer 3

Вот мое принятое решение.Его оценка составляет 1,51 с, 2,6 млн.Не самый лучший, но, может быть, он тебе поможет.

#include <iostream>
using namespace std;

void calculateTrailingZerosOfFactoriel(int testNumber)
{

    int numberOfZeros = 0;
    while (true) 
    {

        testNumber = testNumber / 5;
        if (testNumber > 0) 
            numberOfZeros += testNumber;
        else
            break;
    }
    cout << numberOfZeros << endl;
}

int main() 
{

    //cout << "Enter number of tests: " << endl;
    int t;
    cin >> t;

    for (int i = 0; i < t; i++) 
    {
        int testNumber;
        cin >> testNumber;
        calculateTrailingZerosOfFactoriel(testNumber);
    }
    return 0;
}

Answer 4

Знает, что это более 2 лет, но вот мой код для дальнейшего использования:

#include <cmath>
#include <cstdio>

inline int read()
{
    char temp;
    int x=0;
    temp=getchar_unlocked();
    while(temp<48)temp=getchar_unlocked();
    x+=(temp-'0');
    temp=getchar_unlocked();
    while(temp>=48)
    {
        x=x*10;
        x+=(temp-'0');
        temp=getchar_unlocked();
    }
    return x;
}
int main()
{
    int T,x,z;
    int pows[]={5,25,125,625,3125,15625,78125,390625,1953125,9765625,48828125,244140625};
    T=read();
    for(int i=0;i<T;i++)
    {
        x=read();
        z=0;
        for(int j=0;j<12 && pows[j]<=x;j++)
            z+=x/pows[j];
        printf("%d\n",z);
    }
    return 0;
} 

Это бежало в 0,13 с

Answer 5

Этот вопрос от codechef.

http://www.codechef.com/problems/FCTRL

Как насчет этого решения:

#include <stdio.h>

int a[] = {5, 25, 125, 625, 3125, 15625, 78125, 390625, 1953125, 9765625, 48828125, 244140625};

int main()
{
    int i, j, l, n, ret = 0, z;
    scanf("%d", &z);
    for(i = 0; i < z; i++)
    {
        ret = 0;
        scanf("%d", &n);
        for(j = 0; j < 12; j++)
        {
            l = n / a[j];
            if(l <= 0)
                break;
            ret += l;
        }
        printf("%d\n", ret);
    }
    return 0;
}

Какие-либо оптимизации ???

Answer 6

#include <cstdio>

int main(void) {
    long long int t, n, s, i, j;
    scanf("%lld", &t);
    while (t--) {
        i=1; s=0; j=5;
        scanf("%lld", &n);
        while (i != 0) {
            i = n / j;
            s = s + i * (2*j + (i-1) * j) / 2;
            j = j * 5; 
        }
        printf("%lld\n", s);
    }
    return 0;
}

Answer 7

Вы уже точно знаете правильный алгоритм. Узким местом в вашем коде является использование cin / cout. При работе с очень большими входами cin работает очень медленно по сравнению с scanf.

scanf также медленнее, чем прямые методы чтения ввода, такие как fread, но использование scanf достаточно для решения практически всех проблем в онлайн-судьях.

Это подробно описано в FAQ по Codechef , который, вероятно, стоит прочитать первым;)