P13268 [GCJ 2014 Finals] Allergy Testing

Kelly 对某种食物过敏，但她不确定是哪一种。在她面前有 $\mathrm{N}$ 种不同的食物，而她恰好只对其中一种过敏。为了找出是哪一种，她决定进行一系列实验。 在每次实验中，Kelly 会选择若干种食物一起食用。然后她会等待 $\mathrm{A}$ 天，以观察自己是否会出现过敏反应： - 如果没有反应，她就可以确定自己**不对**这些食物中的任意一种过敏； - 如果出现了反应，她就必须等待反应完全消退，整个过程总共需要 $\mathrm{B}$ 天（从食用食物的那一刻算起）。 为简化实验安排，Kelly 决定：**每次实验必须在上一次实验完全结束（无论是等待 $\mathrm{A}$ 天或 $\mathrm{B}$ 天）后才能进行**。 在每次实验开始前，Kelly 可以根据之前实验的结果自由选择这一次要食用的食物集合。 她希望设计一套实验策略，在最坏情况下，也能尽可能快地确定自己对哪一种食物过敏。 请你计算：在最坏情况下，Kelly 最少需要多少天才能确定她对哪一种食物过敏？

第一行是测试用例个数 $\mathrm{T}$。接下来是 $\mathrm{T}$ 个测试用例。 每个测试用例占一行，包含三个用空格分隔的整数 $\mathrm{N}, \mathrm{A}, \mathrm{B}$，分别表示食物总数、无过敏反应等待天数、以及有过敏反应时总的等待天数。

对于每个测试用例，输出一行，格式为 `"Case #x: y"`，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是 Kelly 在最坏情况下确定过敏源所需的总天数。

在第一个样例中： - 第一次实验：吃食物 #1 和 #2； - 如果 5 天后无反应，则进行第二次实验，吃食物 #3； - 再等 5 天后，如果无反应，则说明过敏的是食物 #4； - 如果有反应，则在第 10 天得知自己过敏于食物 #3； - 如果第一次实验后出现过敏反应，那么在第 7 天（反应消退）后进行第二次实验，吃食物 #1； - 再过 5 天，无反应说明是食物 #2 过敏，有反应说明是食物 #1； - 因此，最坏情况下是第 12 天得出结论。 ## 限制条件 - $1 \leq T \leq 200$ ### Small 数据集（15 分） - 时间限制：~~60~~ 3 秒 - $1 \leq N \leq 10^{15}$ - $1 \leq A \leq B \leq 100$ ### Large 数据集（35 分） - 时间限制：~~120~~ 5 秒 - $1 \leq N \leq 10^{15}$ - $1 \leq A \leq B \leq 10^{12}$ 翻译由 ChatGPT-4o 完成