tyvj P4877 _1．组合数

时间限制：1s

内存限制：256MB

【问题描述】

从m个不同元素中，任取n(n≤m)个元素并成一组，叫做从m个不同元素中取出n个元素的一个组合；从m个不同元素中取出n(n≤m)个元素的所有组合的个数，叫做从m个不同元素中取出n个元素的组合数，记作C(m,n)。

你的任务是：计算C(m,n)末尾有几个0。如C(10,1)=10，末位有一个0。

【输入】

输入文件名为zero.in。

第一行一个数T(<=1000)，表示数据组数

对于每一组数据：输入两个数，m和n

【输出】

输出文件名为zero.out。

对于每组数据输出一行，包含一个数，表示C(m,n)末尾有几个0

【输入输出样例】

zero.in

zero.out

10 1

11 7

20 4

【数据说明】

对于30%的数据，1<=m<=20；

对于70%的数据，1<=m<=1000

对于100%的数据，1<=m<=1000000

思路：

　　就是根据C（m,n)=m! / ( n! * (m-n)! ), 分解因数2，和5.

#include<iostream>

#include<cstdio>

#include<queue>

#include<vector>

#include<algorithm>

#include<cstring>

using namespace std;

int t,n,m;

long long sum[],ans;

void work(long long  x,long long  y)

{

    long long p=;

    while(p<=x)

    {

        sum[]+=y*(x/p);

        p=p*;

    }

    p=;

    while(p<=x)

    {

        sum[]+=y*(x/p);

        p=p*;

    }

}

int main()

{

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d%d",&n,&m);

        sum[]=sum[]=;

        work(n,);

        work(n-m,-);work(m,-);

        ans=min(sum[],sum[]);

        printf("%d\n",ans);

    }

    return ;

}

巴特西

tyvj P4877 _1．组合数

最新文章

热门文章