CSU1021组合数末尾的零

素颜马尾好姑娘i 2022-05-27 08:18 127阅读 0赞

# [1021: 组合数末尾的零][1021_] #

Submit Page  Summary  Time Limit: 1 Sec  Memory Limit: 128 Mb  Submitted: 710  Solved: 478

--------------------

## Description ##

从*m*个不同元素中取出*n* (*n* ≤ *m*)个元素的所有组合的个数，叫做从*m*个不同元素中取出*n*个元素的组合数。组合数的计算公式如下:

C(*m*, *n*) = *m*!/((*m* \- *n*)!*n*!)

现在请问，如果将组合数C(*m*, *n*)写成二进制数，请问转这个二进制数末尾有多少个零。

## Input ##

第一行是测试样例的个数T，接下来是T个测试样例，每个测试样例占一行，有两个数，依次是*m*和*n*，其中*n* ≤ *m* ≤ 1000。

## Output ##

分别输出每一个组合数转换成二进制数后末尾零的数量。

## Sample Input ##

24 21000 500

## Sample Output ##

16

## Hint ##

## Source ##

中南大学第四届大学生程序设计竞赛

对于任意一个数，只有它乘以2才能使它的二进制数后面多一个0

对于n!， 需要找出从1到n这些数中的所有数的二进制有多少个0，再加起来就行了

#include<cstdio> 
    int p(int n)
    {
    	int sum=0;
    	for(int i=1;i<=n;i++)
    	{
    		int x=i;
    		while(x)
    		{
    			if(x&1)	break;
    			sum++;
    			x>>=1;
    		}
    	}
    	return sum;
    }
    int main()
    {
    	int n,m,t;
    	scanf("%d",&t);
    	while(t--)
    	{
    		scanf("%d %d",&n,&m);
    		printf("%d\n",p(n)-p(n-m)-p(m));
    	}
    	return 0;
    }

[1021_]: http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1021

发表评论取消回复

表情：

评论列表（有 0 条评论，127人围观）

还没有评论，来说两句吧...

相关阅读

相关 1000！结果中零的个数，尾部零的个数，例如：8！末尾出现零的个数为1，总的出现零的个数为2

这里考察一个知识点：整数中表示无穷大的整数，那么这个整数怎么表示呢！在JAVA中表示无穷大的整数使用BigInteger 来表示 JAVA 语言code im

àì夳堔傛蜴生んèń/ 2024年02月19日 21:33/ 0 赞/ 70 阅读

相关组合数

1 const ll mod=1e9+7; 2 ll qpow(ll a,ll b) 3 { 4 ll c=1; 5

刺骨的言语ヽ痛彻心扉/ 2023年06月05日 12:33/ 0 赞/ 46 阅读

相关 javascript 去掉小数末尾多余的零

最近做项目需要对金额进行千分位处理的同时，保留多位小数。但是，小数部分不得为零。 let num1 = 995092130000000 / 100000000000

系统管理员/ 2022年12月30日 08:13/ 0 赞/ 210 阅读

相关组合数的计算

组合数的计算 Time Limit: 2000ms Memory limit: 32768K 有疑问？点这里^\_^ 题目描述给定n组整数(a,b)，计算组

太过爱你忘了你带给我的痛/ 2022年08月10日 04:58/ 0 赞/ 218 阅读

相关组合数

组合数时间限制： 3000 ms | 内存限制： 65535 KB 难度： 3 描述找出从自然数1、2、... 、n（0<n<10）中任取r(0<r<=n)

Love The Way You Lie/ 2022年08月05日 07:26/ 0 赞/ 228 阅读

相关组合数

组合数时间限制： 3000 ms | 内存限制： 65535 KB 难度： 3 描述找出从自然数1、2、... 、n（0<n<10）中任取r(0<r<=n)

怼烎@/ 2022年07月12日 13:14/ 0 赞/ 228 阅读

相关 CSU----E: 删数游戏

ACM小组喜欢上了一个无聊的游戏，游戏的过程是输入一个正整数n，去掉n的任意S个数字后，把剩下的数字看作是一个新的整数（去除前导零）。对给定的N和S，寻找一种删数规则使得剩下的

「爱情、让人受尽委屈。」/ 2022年06月14日 02:37/ 0 赞/ 183 阅读

相关 CSU1021组合数末尾的零

[1021: 组合数末尾的零][1021_] Submit Page Summary Time Limit: 1 Sec Memory Limit: 128 Mb

素颜马尾好姑娘i/ 2022年05月27日 08:18/ 0 赞/ 128 阅读

相关 CSU 2167

题意：初始有n\m的点，矩形排列。有2种操作，第一种是将第i行的所有点联通（a<=i<=b）,第二种是将第i列的所有点联通（a<=i<=b）。每次操作后输出有多少个联通块。

电玩女神/ 2022年01月26日 14:55/ 0 赞/ 227 阅读

相关一个阶乘中末尾零的个数

//给定一个正整数n，请计算n的阶乘n！末尾所含有“0”的个数。 5！=120，其末尾所含有的“0”的个数为1； 10！= 3628800，其末尾所含有的“

分手后的思念是犯贱/ 2022年01月05日 23:19/ 0 赞/ 308 阅读