CSU->1021: 組合數末尾的零

1021: 組合數末尾的零

Time Limit: 1 Sec     Memory Limit: 128 Mb    
           

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

2

4 2

1000 500

Sample Output

1

6

Hint

Source

中南大學第四屆大學生程式設計競賽

題目連結：http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1021

題解：由題目的描述可知組合數的定義。求一個數的二進制末尾0的個數實際上是求這個數可以被2整除多少次，也就是有多少個2的因子。依題目意思，ans=m！因子2的個數-（m-n）！因子2的個數-n！因子2的個數。

AC代碼：

#include<iostream>
using namespace std;

int fun(int m){
    int num=;
    while(m){
        int tmp=m;
        while(tmp){
            if(tmp&){
                break;
            }
            num++;
            tmp>>=;
        }
        m--;
    }
    return num; 
}

int main(){
    int T;
    scanf("%d",&T);
    int m,n;
    int num;
    while(T--){
        scanf("%d%d",&m,&n);
        num=fun(m)-fun(m-n)-fun(n);
        if(num>){
            printf("%d\n",num);
        }
        else{
            printf("0\n");
        }   
    }
    return ;
}