Permutation and binary (Ji, DA) (day 84)

1： subject

ji Lin Big xue Computer test questions

 In combinatorics , We learned permutation numbers .

 from  n  Take out... Of the different elements  m（m<=n） The number of all permutations of elements , It's called from  n  To take  m  Number of permutations of , Write it down as  p(n,m).

 The specific calculation method is  p(n,m)=n(n−1)(n−2)……(n−m+1)=n!/(n−m)!（ Regulations  0!=1）.

 When  n  and  m  Not very young , This permutation number is a relatively large number , such as  p(10,5)=30240.

 If expressed in binary, it is  p(10,5)=30240=(111011000100000)b, in other words , At the back  5  A zero .

 Our problem is , Given a permutation number , Calculate the number of consecutive zeros following its binary representation .

 Input format 
 Input contains multiple sets of test data .

 Each group of data occupies one row , Contains two integers  n,m.

 Last act  0 0, End of input , No need to deal with .

 Output format 
 Output one row per group of data , A result , Represents the permutation number  p(n,m)  The binary representation of is followed by how many consecutive zeros .

 Data range 
1≤m≤n≤10000,
 The input can contain at most  100  Group data .

 sample input ：
10 5
6 1
0 0
 sample output ：
5
1
 difficulty ： Simple 
 when / Empty limit ：1s / 64MB
 Total number of passes ：681
 Total attempts ：1047
 source ： Jilin University postgraduate entrance examination machine test questions 
 Algorithm tags 

2： Code implementation

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int f(int n, int p)
{
    
    int res = 0;
    while (n) res += n / p, n /= p;
    return res;
}

int main()
{
    
    int n, m;
    while (cin >> n >> m, n)
        cout << f(n, 2) - f(n - m, 2) << endl;
    return 0;
}