codechef实践问题,帮助需要 - 找到一个阶乘尾随零 [英] Codechef practice question help needed - find trailing zeros in a factorial
问题描述
我一直在这方面的工作,现在24小时,试图对其进行优化。现在的问题是如何找到尾随零的一个数字10000000和1000万测试用例范围因子在约8秒的数量。
I have been working on this for 24 hours now, trying to optimize it. The question is how to find the number of trailing zeroes in factorial of a number in range of 10000000 and 10 million test cases in about 8 secs.
在code是如下:
#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;
}
请帮我推荐一个新的方法,或者提出一些修改,这一个。
Please help me by suggesting a new approach, or suggesting some modifications to this one.
推荐答案
使用下面的定理:
如果p是一个素数,则最高 磷动力,其将N! (N 阶乘)为[N / P] + [N / P ^ 2] + [N / P ^ 3] + ... + [N / P ^ k]的,其中k是 P&所述的最大功率; = n,并且[X]是x的整数部分
If p is a prime, then the highest power of p which divides n! (n factorial) is [n/p] + [n/p^2] + [n/p^3] + ... + [n/p^k], where k is the largest power of p <= n, and [x] is the integral part of x.
参考: http://planetmath.org/encyclopedia/PrimePowerDividingAFactorial.html
这篇关于codechef实践问题,帮助需要 - 找到一个阶乘尾随零的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!