【数论】博士与钥匙

博士与钥匙

(n)个持有若干把钥匙的人(每个人持有的钥匙数相同)和若干把锁,任选(m)个人可以打开所有的锁,但小于(m)个人就不能打开所有的锁,给定(n,m),求至少要有多少把锁、每个人至少要配多少把钥匙。

数学题。

由于任选(m)个人可以打开所有的锁,而(<=m-1)个人不能打开所有的锁,不妨设无法打开的其中一把锁为(L),那么可以推出,在选定这(m-1)个人之后,剩下的(n-(m-1))个人都持有(L)的钥匙。从而,对于任意一把锁(L),没有它的钥匙的人为(m-1)个。

由于任意(m-1)个人都不能打开所有的锁,那么锁的数目应为(A=C_n^{m-1}).

对于任意一把锁(L),持有它钥匙的人为(n-m+1)个,由于是最少数目,所以(L)的钥匙总共只有(n-m+1)把,则(n)个人总共持有的钥匙数量为(A imes(n-m+1))把,平均一下即得每个人持有的最少钥匙数(B=frac {A imes(n-m+1)}{n}).

数据范围(1)(20),阶乘运算int会溢出,记得开long long。

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;

typedef long long LL;
LL jc(int n) {
    LL res = 1;
    for (int i = 1;i <= n;i++) res = res * i;
    return res;
}

LL c(int n, int m) {
    return (jc(n)) / (jc(m) * jc(n - m));
}

int main()
{
    int n, m;
    while (cin>>n>>m) {
        LL L = c(n, m - 1);
        LL K = L * (n - m + 1) / n;
        cout << L << " " << K << endl;
    }
    return 0;
}
原文地址:https://www.cnblogs.com/streamazure/p/12770431.html