题解 P1431 【找出伪币】

对于$p!=0$,直接$\lceil log3(n)\rceil$

对于$p=0$,直接$\lceil log3(2\ast n+3)\rceil$

对于高精,直接上python

对于理由,直接看维基链接

对于想偷懒看代码的,直接瞅下面

import math
import itertools
T=input()
T=int(T)
for i in range (T):
   k, p, n = input().split()
   k=int(k)
   p=int(p)
   n=int(n)
   if p!=0:
      t=math.ceil(math.log(n)/math.log(3))  #换底公式
   else:
      t=math.ceil(math.log(n*2+3)/math.log(3))
   print(t)

应篇幅要求，这里感性证明一波：

假设现在只有A B C三枚硬币。

1. 如果现在知道假币的轻重。如果C重些，那么称A B会发现它们一样重，所以可判断C更重；如果A(B)重些，那么称A B也可得到。所以只需一次即可。

2. 如果现在不知道假币的轻重。如果称A B发现它们一样重，只能确定C是假币，还需拿一枚去和C称一下看C是轻是重；如果A B不一样重，也需要拿一枚和C称一下来判断是A B哪个是假币。所以需要两次。

对于任意n枚硬币，最好的方法是尽量三分，然而有时做不到完全平均，可能需要对这一两枚“特殊照顾”再称一次，所以要向上取整。

综上我们可以得到，如果知道轻重，需要称$\lceil log3(n)\rceil$次。

但为甚么不知道轻重时是$\lceil log3(2\ast n+3)\rceil$次呢？

其实很简单，(此处玄学)因为当n=3时两次刚刚好，而n=4时就超了。就相当于$log3(2\ast n+b)=2$ 一样所以这里$b=3$ 啦。