首页 > 试题广场 >

排列与二进制

[编程题]排列与二进制

热度指数：4159 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

在组合数学中，我们学过排列数。从n个不同元素中取出m（m<=n）个元素的所有排列的个数，叫做从n中取m的排列数，记为p(n, m)。具体计算方法为p(n, m)=n(n-1)(n-2)……(n-m+1)= n!/(n-m)! (规定0!=1).当n和m不是很小时，这个排列数是比较大的数值，比如 p(10,5)=30240。如果用二进制表示为p(10,5)=30240=( 111011000100000)b，也就是说，最后面有5个零。我们的问题就是，给定一个排列数，算出其二进制表示的后面有多少个连续的零。

输入描述:

输入包含多组测试数据，每组测试数据一行。
每行两个整数，n和m，0<m<=n<=10000，n=0标志输入结束，该组数据不用处理。

输出描述:

对于每个输入，输出排列数p(n, m)的二进制表示后面有多少个连续的零。每个输出放在一行。

示例1

输入

10 5
6 1
0 0

输出

5
1

算法知识视频讲解

Java

菜鸟葫芦娃

有题目中的公式p(n, m)=n(n-1)(n-2)……(n-m+1)= n!/(n-m)! ,根据数学阶乘算最后得到的p(n,m)=n*(n-1)*(n-2)*(n-3)........*(n-m+1)。比如p(10,5)=10*9*8*7*6*5*4*3*2*1/5*4*3*2*1=10*9*8*7*6;也就是相当于求 10*9*8*7*6 中最后连续0的个数。

由于二进制数乘法过程可仿照十进制数乘法进行。但由于二进制数只有0或1两种可能的乘数位，导致二进制乘法更为简单。二进制数乘法的法则为：

0×0＝0
0×1＝1×0＝0
1×1＝1

例如：1001和1010相乘的过程如下：

由低位到高位，用乘数的每一位去乘被乘数，若乘数的某一位为1，则该次部分积为被乘数；若乘数的某一位为0，则该次部分积为0。某次部分积的最低位必须和本位乘数对齐，所有部分积相加的结果则为相乘得到的乘积。

由于二进制乘法和十进制乘法相似的原理,可知只需要求出每位数中最后零的个数,然后把每位零的个数相加就是最后连续零的结果。

import java.util.Scanner;
public class Main
{
    public static void main(String[] args)
    {
        Scanner in=new Scanner(System.in);
        while(in.hasNextInt())
        {  
            int n=in.nextInt();
            int m=in.nextInt();
            if(n==0)
                break;
            int res=0;
            for(int i=n-m+1;i<=n;++i)
            {
                int tmp=i;
                while((tmp&1)==0)
                {
                    ++res;
                    tmp>>=1;
                }
            }
            System.out.println(res);
        }
        in.close();
    }
}

发表于 2016-08-25 14:42:19 回复(4)

我太想读书

//关键是要知道二进制左移一位相当于乘以二

#include<stdio.h>

int Judge(int x){
    int count = 0;
    while(x%2==0)
    {
        count++;x=x/2;
    }
    return count;
}

int main(){
    int n,m;
    while(scanf("%d %d",&n,&m)!=EOF){
        int count=0;
        for(int i=n-m+1;i<=n;i++)
            count+=Judge(i);
        printf("%d\n",count);
    }
}

发表于 2020-03-18 15:33:29 回复(0)

C/C++

YhX.

//就是n-m+1-----n这一堆数中能整除2多少次 
#include<stdio.h>
(737)#include<math.h>
int main()
{
    int m,n,i,k,num;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n==0&&n==m) break;
        num=0;
        for(i=n-m+1;i<=n;i++)//所有的数
        {
            k=i;
            while(k%2==0)//这个数能整除2
            {
                num++;
                k=k/2;
            }
        }
        printf("%d\n",num);
    }
    return 0;
}

发表于 2020-04-25 18:48:49 回复(0)

VirgilG72

试图用暴力破解此题，把大数加减乘除求余都过一遍了。。。最后居然。。。还是只通过50％case，原来换种思路这么简单。。。还是自己太笨了。。。不过不亏，花一下午研究了大数加减乘除求余。。。希望自己下次能换种角度想问题！

#include <bits/stdc++.h>
using namespace std;
string tmp;

char BignumberMod(string s){
	int mod=0;
	tmp="";
	for(int i=0;i<s.size();i++){
		mod=mod*10+s[i]-'0';
		if((i!=s.size()-1)){
			if(mod<2) {
				if(i==0) continue;
				tmp.push_back('0');
				continue;
			}
			
			 
		} 
	
		 tmp.push_back((char)(mod/2+'0'));
		mod=mod%2;
		if(i==s.size()-1){
			return (char)(mod+'0');
		}
	}
}
int GetBits(string s)
{
	string result;
	int count=0;
//	if(s.size()==1&&s[0]=='0') {
//		cout<<0<<endl;
//		continue;
//	}
//	result.clear();
		while(s.size()>=1){
		//	if(s.size()==1&&stoi(s)==0) break;//巧用短路性 
			if(BignumberMod(s)=='0') count++;
			else break;
			s.assign(tmp);
		//	cout<<s<<endl;
		
			
		}
	

	return count;
}

string addBigNumber(string str1,string str2 ){
	int output[100000];
	int m=str1.size()-1;
	int n=str2.size()-1;
	string result;
	//cout<<m<<" "<<n;
	memset(output,0,sizeof(output));
	for(int i=0;i<=m;i++){
		output[i]=output[i]+(str1[m-i]-'0');
	}
//	for(int i=0;i<=m;i++){
//		cout<<output[i];
//	}
	for(int i=0;i<=n;i++){
		int sum=output[i]+(str2[n-i]-'0');
		//	for(int i=0;i<=m;i++){
//		cout<<output[i];
//	}
	//cout<<sum<<endl;
		output[i]=sum%10;
		if(sum>=10) output[i+1]++;
				
	}
	int size=max(n,m)+1;
	int flag=0;
	//cout<<size;
	for(int i=size;i>=0;i--){
		if(flag==0&&output[i]!=0){
			 flag=1;
	}
	if(flag)
	result.push_back(output[i]+'0');
	}
	reverse(result.begin(),result.end());
	return result;
	
	
	
}

string Bignumbermultiply(string str1,string str2){
	string result1,result2;
	//cin>>str1>>str2;
	int carry=0;
	int i=str1.size()-1;
	int j=str2.size()-1;
//	cout<<i<<" "<<j<<endl;
	if(j!=-1){
		while(i>=0){
		int sum=(str1[i]-'0')*(str2[j]-'0')+carry ;
		result1.push_back(sum%10+'0');
		if(sum>=10)
		carry=(sum/10)%10;
		else carry=0;
		i--;
		}
		if(i==-1&&carry!=0)
		result1.push_back(carry+'0');
	}
	//cout<<result1<<" "<<result2<<endl;
	j--;
	if(j==-1){
			reverse(result1.begin(),result1.end());
			//cout<<result1;
			return result1;
	}
	
	while(j!=-1){
		
	if(j!=-1){
	int	k=str2.size()-1-j;
	while(k--)	result2.push_back('0');
	i=str1.size()-1;
	carry=0;
	while(i>=0){
		int sum=(str1[i]-'0')*(str2[j]-'0')+carry ;
		result2.push_back(sum%10+'0');
		if(sum>=10)
		carry=(sum/10)%10;
		else carry=0;
		i--;
		}
		if(i==-1&&carry!=0)
		result2.push_back(carry+'0');
	}
	reverse(result1.begin(),result1.end());
	reverse(result2.begin(),result2.end());
	//cout<<result1<<" "<<result2<<endl;
	//cout<<addBigNumber(result1,result2);
	result1=addBigNumber(result1,result2);
	result2="";
	j--;
	}
	reverse(result1.begin(),result1.end());
	return result1;
	
}
string Getstringnum(int a){
	string result;
	while(a!=0){
		result.push_back((a%10)+'0');
		a/=10; 
	}
	reverse(result.begin(),result.end());
	return result;
}

int main(){
	int n,m;
	while(cin>>n>>m&&n!=0){
		string l="1";
		int count=0;
		for(int i=1;i<=m;i++){
			//cout<<l<<" "<<Getstringnum(n-i+1)<<endl;
			l=Bignumbermultiply(l,Getstringnum(n-i+1));
		}
 // cout<<Bignumbermultiply("10",Getstringnum(9));
   //cout<<Getstringnum(9);
		cout<<GetBits(l)<<endl;
//		for(int i=0;;i++){
//			if(!GetBits(l,i)) count++;
//			else break;
//		}
//		cout<<count<<endl;
		
	}
	return 0;
}

发表于 2020-03-07 17:11:45 回复(0)

C/C++

算法小屁孩

#include<bits/stdc++.h>
int main(){
    int n,m;
    while(scanf("%d %d",&n,&m)!=EOF && n!=0){
        int sum=0,s=1;
        for(int i=n-m+1;i<=n;i++){
            s=s*i;
            while(s%2==0){
                s/=2;sum++;
            }
        }
        printf("%d\n",sum);
    }
}

发表于 2019-03-20 13:36:32 回复(0)

此人在刷题

不用算阶乘，只需要算1到1000每个数字都有多少个2，然后累加就是阶乘得到的2了

#include<iostream>
using namespace std;
int rec[10001]={0};
void init()
{
rec[2]=1;
for(int i=3,t=0;i<10001;i++)
{
int k=0;
t=i;
while(t>0)
{
if(t%2==0)
{
k++;
t/=2;
}
else break;
}
rec[i]=rec[i-1]+k;
}
}
int main()
{
int n,m;
init();
while(cin>>n>>m)
{
if(n==0&&m==0)break;
cout<<rec[n]-rec[n-m]<<endl;
}
return 0;
}

发表于 2018-08-21 15:06:15 回复(0)

VagrantYang

可能我最菜了，心塞

package com.speical.first;

import java.util.Scanner;
/** 
*
* @author special
* @date 2018年2月2日 上午9:08:30
*/
public class Pro173 {
    static final int MOD = 10000;

    public static int[] factory(int n, int m){
        int[] result = new int[100000];
        int index = 1, carry = 0, temp;
        result[index++] = 1;
        result[0]++;
        for(int i = m; i <= n; i++){
            carry = 0;
            for(int j = 1; j < index; j++){
                temp = i * result[j] + carry;
                result[j] = temp % MOD;
                carry = temp / MOD;
            }
            if(carry > 0){ 
                result[index++] = carry; 
                result[0]++;
            }
        }
        return result;
    }

    public static int getBinary(int[] num){
        int length = num[0], r = 0, count = 0;
        for(int i = length; i > 0;){
            r = 0;
            for(int j = i; j > 0; j--){
                num[j] += r * MOD;
                r = num[j] % 2;
                num[j] /= 2;
            }
            while(i > 0 && num[i] == 0){
                i--;
            }
            if(r != 0){
                break;
            }else{
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner input = new Scanner(System.in);
        while(input.hasNext()){
            int n = input.nextInt();
            int m = input.nextInt();
            if(n == 0) break;
            int[] result = factory(n, n - m + 1);
            System.out.println(getBinary(result));
        }
    }

}

发表于 2018-02-02 09:55:41 回复(0)

263保洁小妹

归根结底就是在问n*(n-1)*……*(n-m+1)能整除几次2。

也就是上述乘积里面能分解出几个2。那么，可以把每个乘数分别判其断能分解出的2的数量，然后加在一起就是乘积能分解出的2的数量。

代码如下：

#include <stdio.h>
#define N 10001
int main()
{
    int m, n, x;
    int count;
    int a[N];//a[i]表示i能分解出几个2
    for(int i=1; i<N; i++)
    {
        a[i]=0;
        x=i;
        while(x%2==0)
        {
            x=x/2;
            a[i]++;
        }
    }
    while(scanf("%d %d", &n, &m)!=EOF)
    {
        if(n==0) break;
        count=0;
        for(int i=n; i>n-m; i--)
        {
            count+=a[i];
        }
        printf("%d\n", count);
    }
    return 0;
}

编辑于 2018-02-08 17:13:46 回复(6)

紫魂的海角

#include<stdio.h>

int main()
{
    int m,n,i,k;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        if(n==0)   break;
        int num=0;
        for(i=n-m+1;i<=n;i++)
        {
            k=i;
            while(k%2==0)
            {
                num++;
                k=k/2;
            }
        }
        printf("%d\n",num);
    }
    return 0;
}

发表于 2017-03-03 11:17:35 回复(2)

小陈也只是想要一个实习罢了

//归根结底就是求出n*(n-1)*...*(n-m+1)一共有多少个2
//所以就每个都除以2直到不为2的倍数为止，也防止乘数过大超出范围
#include<iostream>
using namespace std;
int main(){
    int n,m;
    while(cin>>n>>m){
        if(n==0)
            break;
        int begin=n,end=n-m+1,count=0;
        for(int i=begin;i>=end;i--){
            int temp=i;
            while(temp%2==0){
                count++;
                temp/=2;
            }
        }
        cout<<count<<endl;
    }
}

发表于 2020-01-13 21:11:08 回复(0)

纠结的西红柿

//此题是不能硬按照公式算的。树打了，就会超出计算机的表示范围。他是有思路的。比如一个是十进制数220，它的末尾有一个连续的0，它本身就相当于22*10，即22扩大10倍，即22左移一位，低位补0。因此对于十进制数而言，想知道末尾有多少个连续的0，实质就是去看这个数含有多少个因子10。比如上面220=22*10，其中22虽然比10大，但它没法再分成关于10的因式了，所以只有一个因子10，即末尾含有一个连续的0。而300=3*10*10，含2个因子10，所以末尾有两个连续的0。
//而同理，对于二进制数据而言，它每一次左移一位，低位补0，就相当于它对于的十进制数乘2。所以一个二进制数据末尾有多少个连续的0，就看它左移了多少次，即它的十进制数据含有多少个因子2。
//另外若A=B*C，那么 A中含因子2的个数 = B中含因子2的个数 + C中含因子2的个数，这个不难理解。比如24=4*6=（2*2)*(2*3)=2*2*2*3。
//所以此题我们只需要分别判断n,n-1,n-2,,,,,,n-m+1中分别有多少个因子2，然后把个数加起来就可以了。
#include <iostream>
#include <bitset>
using namespace std;
int CU(int x)
{
    int s=0;
    while(x%2==0)
    {
       s++;
       x=x/2;
    }
    return s;
}
int main() {
    int n, m;
    while (cin >> n >> m)
    {
        if (n == 0)
            break;
        int sum=0;
        for(int i=n-m+1;i<=n;i++)
            sum+=CU(i);
        cout<<sum<<endl;
    }
}

发表于 2023-03-13 15:14:59 回复(0)

C++

牛客844036446号

借鉴了别人的思路，一开始求积超范围了。

#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
    int n,m,a,p;
    while(scanf("%d %d",&n,&m)!=EOF&n!=0&m!=0)
    {
        a=0;
        p=1;
        for(int i=n-m+1;i<=n;++i)
        {
            p=i;
            for(int j=0;j<10000;++j)
            {
                if(p%2==0)
                {
                    a++;
                    p/=2;
                }    
                else
                    break;
            }
        }
        printf("%d\n",a);
    }
}

发表于 2021-09-02 13:03:58 回复(0)

不自量力德还手

从排列组合角度讲，P（10，5）=30240是不是不对啊，不应该是10!/5!/5!吗？高中把这个写成C(m,n)=m!/(m-n)!/n!。

while True:

try:
a,b=map(int,input().split())
if a==0 or a<b:
continue
elif a==b:
print(0)
else:
# if a<(2*b):
# b=a-b
sum=0
for i in range(a,(a-b),-1):
j=1
while(not (i&j)):
sum+=1
j=j<<1
print(sum)
# for i in range(1,b+1,1):
# j=1
# while(not (i&j)):
# sum-=1
# j=j<<1
# print(sum)
except:
break

发表于 2021-06-21 23:54:59 回复(0)

森林蝙蝠

#include<iostream>
#include<cmath>
using namespace std;
int main(){
    int n,m;
    while(cin>>n>>m){
        int arr[m];int sum=0;
        for(int i=0;i<m;i++)
            arr[i]=i+n-m+1;
        for(int j=0;j<m;j++)
            for(int k=13;k>=1;k--){
                int b=pow(2,k);
                if(arr[j]%b==0){
                    sum+=k;break;}
            }
        printf("%d\n",sum);
    }
}

发表于 2021-03-19 23:44:11 回复(0)

C/C++

纠结offer的菜狗

#include<iostream>
using namespace std;

int main()
{
    int n,m,count;
    while(cin >> n >> m && n && m)
    {
        count = 0;
        int t = 1;
        for(int i = n;i > n - m;i--)
        {
            t *= i;
            while(t % 2 == 0)
            {
                t /= 2;
                count++;
            }
        }
        cout << count << endl;
    }
    return 0;
}

发表于 2021-02-22 18:15:33 回复(0)

C/C++

KDDA十三尧十三

#include<iostream>
using namespace std;
#define max 10001
//二进制表示，算术左移即为乘2，右边补0；
//只需右移即除2，找到第一个二进制位为1的就行,右移次数即为0的个数
int main(void)
{
    int m,n;
    int count = 0;
    
    while(cin >> n >> m)
    {
        if(n == 0)
            break;
        else if(n < max || m < max)
        {
            for(int i = n - m + 1;i <= n;i++)
            {
                int temp = i;
                while(temp % 2 == 0)
                {
                    count++;
                    temp /= 2;
                }
            }
            cout << count << endl;
        }
    }
    return 0;
}

发表于 2021-01-30 13:57:25 回复(0)

C/C++

不偷不抢安度因_

#include <stdio.h>
#include <stdlib.h>

int count;

int main()
{
    int m, n;
    while(~scanf("%d", &n))
    {
        if(!n)
            break;
        scanf("%d", &m);
        count = 0;
        while(m--)
        {
            int tmp = n;
            while(tmp % 2 == 0)
            {
                count++;
                tmp /= 2;
            }
            n--;
        }
        printf("%d\n", count);
    }

    return 0;
}

编辑于 2020-04-19 20:59:59 回复(0)

zbkhzd

动态规划

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    while(cin>>n>>m&&n)
    {
        vector<int> dp(n+1,0);
        int res=0;
        for(int i=1;i<=n;++i)
        {
            if(2*i<=n)dp[2*i]=dp[i]+1;
            if(i>=n-m+1)res+=dp[i];
        }
        cout<<res<<endl;
    }
    return 0;
}

发表于 2020-04-19 14:04:27 回复(0)

hikariion

#include<iostream>
using namespace std;
int two(int x){
	x = x & (-x);
	int cnt = 0;
	while(x>0){
		if(!(x&1==1)) cnt++;
		x = x >> 1;
	}
	return cnt;
}
int main(){
	int n,m;
	while(cin >> n >> m){
		if(n==0) return 0;
		else {
			int sum  = 0 ;
			for(int i=n;i>=n-m+1;i--){
				sum += two(i);
			}
			printf("%d\n",sum);
		}
		
	}
	
	return 0;
}

发表于 2020-04-07 11:44:27 回复(0)

牛客982383849号

#include <iostream>
using namespace std;
int fact(int n){
    int counts = 0;
    while(n != 0){
        counts += n / 2;
        n /= 2;
    }
    return counts;
}

int main() {
    int x, y;
    while(cin >> x >> y){
        if(x == 0 && y == 0){
            break;
        }
        cout<<fact(x) - fact(x - y)<<endl;
    }

    return 0;
}

发表于 2020-04-01 16:15:50 回复(0)