T2 危险の试剂：数论

题意说明

就是让你求出弹珠最多能在试剂瓶里分裂几次，如果不能激活就输出 $-1$。

体积公式

在特殊说明部分已经给出了球体、直圆柱体的体积计算公式了，直接带入即可。需要注意的是，由于 $\pi$ 和 $\frac{4}{3}$ 是小数，因此需要使用 double 进行存储。

球体体积计算公式如下：

$$V_1=\frac{4}{3}\pi{r_1}^3$$

直圆柱体体积计算公式如下：

$$V_0=\pi{r_0}^2h$$

特殊说明部分已说明不计球体之间的空隙，因此试剂瓶最多可以容纳 $\lfloor \frac{V_1}{V_0}\rfloor$ 个球。当可容纳球的数量不足 $1$ 个时，说明不能激活，直接输出 $-1$。

代入计算：

double qiu = (4 / 3.0) * 3.14 * r1 * r1 * r1;
double yuanzhu = 3.14 * r0 * r0 * h;
long long maxx = floor(yuanzhu / qiu);
if(maxx < 1){
    cout << -1 << endl;
    continue;
}

特殊性质 A

因为在这个性质中，$h=r_0=k=r_1$，通过简单的计算可得：

$$maxx\lt1$$

因此不可以所有药剂都不可激活，全部输出 $-1$ 即可。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int T; cin >> T;
    while(T--){
        cout << -1 << endl;
    }
    return 0;
}

时间复杂度：$O(T)$

预计得分：$28pts$

正解 | 枚举法（推荐）

由于 $k$ 值的范围较小（$\le10^6$），可以直接采用枚举的方式找出最多可以分裂多少次，其时间是 $log$ 级的。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int T; cin >> T;
    while(T--){
        long long h,r0,k,r1; cin >> h >> r0 >> k >> r1;
        double qiu = (4 / 3.0) * 3.14 * r1 * r1 * r1;
        double yuanzhu = 3.14 * r0 * r0 * h;
        if(qiu > yuanzhu){
            cout << -1 << endl;
            continue;
        }
        long long maxx = floor(yuanzhu / qiu),have = 1,ans = 0;
        for(int i = 1;have <= maxx;i++){
            have *= k;
            ans++;
        }
        if(have > maxx) cout << ans - 1 << endl;
        else cout << ans << endl;
    }
    return 0;
}

时间复杂度：$O(T\times log_k^{\frac{yuanzhu}{qiu}})$

预计得分：$120pts$

正解 | 数学法

我们可以采用换底公式来解答这个问题。根据换底公式：

$$\log_bN=\frac{\log_aN}{\log_ab}$$

可得，篮球最多可分裂的秒数是：

$$\log s=\lfloor\frac{\log maxx}{\log k}\rfloor$$

在此之后，我们需要验证计算结果是否超过实际分裂的最大数量，如果分裂秒数为负数，则直接设为 $-1$。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int T; cin >> T;
    while(T--){
        long long h,r0,k,r1; cin >> h >> r0 >> k >> r1;
        double qiu = (4 / 3.0) * 3.14 * r1 * r1 * r1; // 球体体积计算
        double yuanzhu = 3.14 * r0 * r0 * h; // 直圆柱体体积计算
        long long maxx = floor(yuanzhu / qiu); // floor：向下取整
        if(maxx < 1){ // 可容纳少于一个篮球
            cout << -1 << endl;
            continue; // 提前结束
        }
        double s = log(maxx) / log(k); // 换底公式
        long long l = floor(s); // 向下取整
        cout << l << "\n";
    }
    return 0;
}

时间复杂度：$O(T)$

预计得分：$120pts$

注意：虽然这份代码时间复杂度更低，但是由于多次的数学计算，可能导致精度丢失，面对没有 Special Judge 的或者精度要求更高的题目题目可能会 WA，所以不推荐这种解法。