出题人作为苦逼的研究生被导师布置了一项任务，他的面前摆有n件物品，这n件物品中仅有一件物品比其他物品重。而出题人则拥有一个神奇天平，该天平最多可以放置m样东西，每次称量可以得出哪样东西最重，或者放置的若干样东西一样重。
现在出题人想知道，他至少称多少次一定能找出这件较重的物品？
问题 H: 神奇天平
时间限制: 1 Sec 内存限制: 128 MB提交: 0 解决: 57
[提交][状态][讨论版][命题人:]
题目描述
输入描述
第一行一个正整数T，表示数据组数T≤1e5。
对于每组数据，输入两个整数n,m，2≤n≤1e9,2≤m≤1e9。
对于每组数据，输入两个整数n,m，2≤n≤1e9,2≤m≤1e9。
输出描述
对于每组数据，输出保证一定能找到较重物品的最少称量次数。
样例输入
2
9 2
8 2样例输出
2
2提示
对于样例1：
首先把9件物品分成三堆，每堆3件，然后将其中两堆放入神奇天平。若一样重则表示重的物品在没放入的那堆中，否则通过天平我们可以找到重的那堆。
把重的那堆三件物品中的其中两件再次放入神奇天平，若一样重则表示剩下的那件物品就是重的物品，否则通过天平我们可以找到重的那件物品。
样例2的答案可类比以上过程得到。
-
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部
关于网站改版