时间限制：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 |
|
3 10 1 11 7 20 4 |
1 1 0 |
【数据说明】
对于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[4],ans; void work(long long x,long long y) { long long p=2; while(p<=x) { sum[1]+=y*(x/p); p=p*2; } p=5; while(p<=x) { sum[2]+=y*(x/p); p=p*5; } } int main() { scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); sum[1]=sum[2]=0; work(n,1); work(n-m,-1);work(m,-1); ans=min(sum[1],sum[2]); printf("%d ",ans); } return 0; }