spoj factorial（超出时间限制错误）。 我该如何改进我的解决方案？
这是我关于spoj的问题的链接。
我已经尝试使用递归和非递归。 但我超时限制错误。 我该如何改进我的解决方案？
我已经展示了以下两种解决方案。
A）非递归方法。
#include int main() { long long int t,n,i,j=0,y; unsigned long long int fact; scanf("%lld",&t); i=t; while(i>0) { scanf("%lld",&n); fact=1; for(y=1;y<=n;y++) fact=fact*y; j=0; while(fact%10==0) j++; printf("\n%lld",j); i--; } return 0; } B）非递归
#include unsigned long long int fact(long long int); int main() { long long int t,n,i,j=0; unsigned long long int y; scanf("%lld",&t); i=t; while(i>0) { scanf("%lld",&n); y=fact(n); j=0; while(y%10==0) j++; printf("\n%lld",j); i--; } return 0; } unsigned long long int fact(long long int m) { if(m==0) return 1; else return (m*fact(m-1)); }
问题减少到n中找到10的力量！ （n的阶乘），但为此我们必须找到2和5的幂，因为10个因素分解为2和5
k1= [n/2] + [n/4] + [n/8] + [n/16] + .... k2= [n/5] + [n/25] + [n/125] + [n/625] + .... where as [x] is greatest integer function k1= power of 2 in n! k2= power of 5 in n! ans=min(k1,k2)
但我们仍然存在的问题是我们每次都计算2和5的功率。 怎么避免呢？ 因为我们必须按权力划分。
1. for 2 , sum=0 2. keep dividing n by 2 (sum+=n/2 and n=n/2) 3. and keep on adding the quotient to sum until n becomes 0. 4. finally sum will give power of 2 in n!
重复这个5，两者中最小的将是答案。
工作守则：
// Shashank Jain #include #include #define LL long long int using namespace std; LL n; LL power(LL num) { LL sum=0,m,temp; m=n; while(m>0) { temp=m/num; sum+=temp; m/=num; } return sum; } int main() { int t; LL k1,k2,ans; scanf("%d",&t); while(t--) { scanf("%lld",&n); k1=power(2); k2=power(5); ans=min(k1,k2); printf("%lld\n",ans); } return 0; } // Voila
运行代码链接： Ideone代码链接
我刚刚提交了0.54秒和2.6 MB的AC
这是一个提示 – n末尾的零数！ 由10分干净的次数给出！ 这相当于5除以n的最小次数！ 和2次分割的次数！ 尝试看看你是否可以直接计算这些值，而不是试图计算n !,因为即使是合理的n（比方说，n = 100）n的值！ 是太大了，不适合long long ，你会得到错误的答案。
希望这可以帮助！
//count n! tail zero //count the number of 5 in the prime factor. int noz(int n){ int count; if(n < 5) return 0; count = n / 5; return count + noz(count); }
约束是：
1 <= N <= 1000000000
但是N! 不适合64位整数（在计算机内存中也不适合）。 由于您无法计算因子本身，因此您必须找到另一种方法。 这个页面提供了一个严肃的提示。