Необходимая помощь вопроса о практике Codechef - находит конечные нули в факториале
Я работал над этим в течение 24 часов теперь, пытаясь оптимизировать его. Вопрос состоит в том, как найти количество конечных нулей в факториале числа в диапазоне 10 000 000 и 10 миллионов тестовых сценариев приблизительно в 8 secs.
Код следующие:
#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;
}
Помогите мне путем предложения нового подхода или предложения некоторых модификаций этому.
3 ответа
Используйте следующую теорему:
Если p простое число, то наивысшая степень числа p, делящего n! (n факториал) равно [n / p] + [n / p ^ 2] + [n / p ^ 3] + ... + [n / p ^ k], где k - наибольшая степень p <= n, а [x] - целая часть x.
Ссылка: http://planetmath.org/encyclopedia/PrimePowerDividingAFactorial.html
Оптимальное решение выполняется в O (log N) время, где N - это число, для которого вы хотите найти нули. Используйте эту формулу:
Нули (N!) = N / 5 + N / 25 + N / 125 + ... + N / 5 ^ k , пока деление не станет равным нулю. Подробнее на википедия .
Так, например, в C это будет:
int Zeroes(int N)
{
int ret = 0;
while ( N )
{
ret += N / 5;
N /= 5;
}
return ret;
}
Это будет выполняться за 8 секунд на достаточно быстром компьютере. Вероятно, вы можете ускорить его, используя таблицы поиска, хотя я не уверен, сколько памяти у вас доступно.
Вот еще один совет: не храните числа, они вам не нужны! Подсчитайте количество нулей для каждого числа, когда вы его прочитаете.
Если это для онлайн-судьи, то, по моему опыту, онлайн-судьи завышают временные рамки для решения проблем, поэтому вам придется прибегать к уродливым хитростям, даже если у вас есть правильный алгоритм. Один из таких уродливых приемов - не использовать такие функции, как cin и scanf , а вместо этого использовать fread для одновременного чтения кучи данных в массиве символов, затем проанализируйте эти данные (НЕ используйте sscanf или строковые потоки) и получите из них числа. Уродливо, но обычно намного быстрее.
Вы явно уже знаете правильный алгоритм. Узким местом в вашем коде является использование cin / cout. При работе с очень большими входными данными cin работает очень медленно по сравнению со scanf.
scanf также медленнее, чем прямые методы чтения ввода, такие как fread, но использование scanf достаточно для почти всех задач онлайн-судей.
Это подробно описано в FAQ Codechef , который, вероятно, стоит прочитать в первую очередь;)