VEXOBEN
Vexoben
Apr 11, 2019
It takes 5 minutes to read this article.

题目链接:51nod1306 高楼和棋子

(刷新以获取数学公式)

题意

有个层的高楼和若干个棋子,所有的棋子都是一样的。棋子从楼的某层扔到地上不会碎,但从比这个楼层高的地方扔到地上都会碎。给出楼的高度,以及棋子的数量,你来找出这个,问最坏情况下需要实验多少次才能计算出准确的E(如果棋子摔碎了,就不能继续用这个棋子进行测试了)。

数据范围:组数据,

题解

层楼高,还剩颗棋子的最小步数,那么有

容易发现,相同时,对于很长的一段函数值可能是相同的。

表示颗棋子次实验可以保证测出的最高楼高。

打个表:

可以发现,从而可以推断出是一个关于次多项式。

的时候手工解出来,的时候只需要不多的项就会到,直接预处理出来即可。

的情况:

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL long long
#define pii pair<int, int>
using namespace std;
const int N = 1e6 + 10;

template <typename T> void read(T &x) {
	int f = 0;
	register char c = getchar();
	while (c < '0' || c > '9') f |= (c == '-'), c = getchar();
	for (x = 0; c >= '0' && c <= '9'; c = getchar())
		x = (x << 3) + (x << 1) + (c ^ '0');
	if (f) x = -x;
}

LL lim[65];
vector<LL> f[65];

void init() {
	for (int i = 1; i <= 64; ++i) {
		lim[i] = 1e18;
		f[i].push_back(0);
		for (int j = 1; j < N; ++j) {
			LL tmp = f[i][j - 1] + 1;
			if (i > 1) tmp += f[i - 1][j - 1];
			f[i].push_back(tmp);
			if (f[i][j] > 1e18) {
				f[i][j] = 1e18;
				lim[i] = j;
				break;
			}
		}
	}
}

void solve() {
	LL n, m;
	read(n); read(m);
	if (m == 1) printf("%lld\n", n);
	else if (m == 2) {
		__int128 L = 1, R = n, ans = 0;
		while (L <= R) {
			__int128 mid = (L + R) / 2;
			__int128 tmp = mid * (mid + 1) / 2;
			if (tmp >= n) {
				R = mid - 1;
				ans = mid;
			}
			else L = mid + 1;
		}
		printf("%lld\n", (LL) ans);
	}
	else if (m == 3) {
		__int128 L = 1, R = 1e8, ans = 0;
		while (L <= R) {
			__int128 mid = (L + R) / 2;
			__int128 tmp = (mid * mid * mid + mid * 5) / 6;
			if (tmp >= n) {
				ans = mid;
				R = mid - 1;	
			}
			else L = mid + 1;
		}
		printf("%lld\n", (LL) ans);
	}
	else {
		int L = 1, R = lim[m], ans = 0;
		while (L <= R) {
			int mid = (L + R) >> 1;
			if (f[m][mid] >= n) {
				ans = mid;
				R = mid - 1;	
			}
			else L = mid + 1;
		}
		printf("%d\n", ans);
	}
}

int main() {
	init();
	int T;
	read(T);
	while (T--) solve();
	return 0;
}