UVa 1649 Binomial coefficients 数学

题意：

\(C(n, k) = m(2 \leq m \leq 10^{15})\)，给出\(m\)求所有可能的\(n\)和\(k\)。

分析：

设\(minK = min(k, n - k)\)，容易看出\(minK\)的值绝对不会太大。

因为\(n \geq 2minK\)，经过简单的计算可以知道\(minK\)不超过\(26\)。

所以，可以枚举\(minK\)，二分\(n\)来求解，二分的范围是\([minK,m]\)。

二分的过程中需要比较\(C(n,k)\)和\(m\)的大小，因为\(C(n,k)\)可能会太大超过\(long \, long\)的范围，不能直接计算。

所以可以做除法来比较，\(C(n,k)=\prod\limits _{i=1}^k \frac{n-i+1}{i}\)。

用\(m\)逐个去除以\(\frac{n-i+1}{k}\)，如果过程中变为了\(0\)，说明\(C(n,k)>m\)。

否则\(C(n,k)\)在\(long \, long\)的范围，可以直接计算去比较。

还想到一种(没卵用)优化：

因为\(C(m,1)\)和\(C(m,m-1)\)是显然的一组解，直接加到答案里就好了。

可以从\(minK=2\)开始枚举，\(C(n,2)=\frac{n(n-1)}{2}=m\)。

所以如果有解的话，\(n\)的取值大概在\(\sqrt{2m}\)附近，减少了大概一半的二分次数。

进一步\(minK=3\)的话，\(n\)的范围就更小了，从这个角度我们也可以验证解不会太多。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

#include <utility>

#include <cmath>

using namespace std;

typedef long long LL;

typedef pair<LL, LL> PLL;

vector<PLL> ans;

int cmp(LL n, int k, LL m) {

	LL C = 1;

	for(int i = 1; i <= k; i++) {

		if(m * i / (n - i + 1) / C == 0) return 1;

		C = C * (n - i + 1) / i;

	}

	return C == m ? 0 : -1;

}

void output(const PLL& x) {

	printf("(%lld,%lld)", x.first, x.second);

}

int main()

{

	int T; scanf("%d", &T);

	while(T--) {

		LL m; scanf("%lld", &m);

		ans.clear();

		ans.push_back(make_pair(m, 1LL));

		ans.push_back(make_pair(m, m - 1LL));

		for(int i = 2; i <= 30; i++) {

			LL L = i, R = m;

			while(L <= R) {

				LL mid = (L + R) / 2;

				int c = cmp(mid, i, m);

				if(c == 0) {

					ans.push_back(make_pair(mid, i));

					ans.push_back(make_pair(mid, mid - i));

					break;

				} else if(c == 1) R = mid - 1;

				else L = mid + 1;

			}

		}

		sort(ans.begin(), ans.end());

		ans.resize(unique(ans.begin(), ans.end()) - ans.begin());

		printf("%d\n", ans.size());

		if(!ans.empty()) output(ans[0]);

		for(int i = 1; i < ans.size(); i++) {

			printf(" "); output(ans[i]);

		}

		printf("\n");

	}

	return 0;

}

巴特西

UVa 1649 Binomial coefficients 数学

题意：

分析：

最新文章

热门文章