sdut3138: N!(计算n!中结尾零的个数）

题目：http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=3138

算法思想：在1-10两个数相乘要产生0，只有 10×1=2×5，2×5。

200！=200×199×198……×2×1=2×5×2×5×2×199…. ×2×1;可以分解为质数相乘的形式,很明显有2的个数比5的多(2*5=10),所以只要求出200的阶乘可分解出多少个质因子5,就可得到200的阶乘结尾的连续的零的个数.

即:num=[200/5]+[200/5/5]+[200/5/5/5].

注: [x]表示对x取整.

代码：

#include <iostream>

#include <string.h>

#include <stdio.h>

#include <algorithm>

#include <math.h>

#include <map>

#include <queue>

typedef long long  ll;

#define inf 0x3f3f3f3f

using namespace std;

ll sum;

int main()

{

    int T,K=,n;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        sum=;

        while(n)

        {

            sum+=n/;

            n/=;

        }

        printf("Case #%d: %lld\n",++K,sum);

    }

    return ;

}

巴特西

sdut3138: N!(计算n!中结尾零的个数）

最新文章

热门文章