题解 | #C 小数字#

C 小数字

当 $n$ 足够大的时候， $\lceil \sqrt{n}\rceil \lt \lceil \frac{n}{2}\rceil \lt n-1$ 。

当 $n$ 小到一定程度时，以上大小关系才会发生一定变化。

并且当 $n \lt 0$ 时，我们发现只有 $n-1$ 的操作可以让 $n$ 减少。

所以我们定一个界限（比如10），然后大范围开根号，小范围判断，小于0的时候直接计算即可。

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    while(m -- ) {
        if (n >= 10) {
            n = ceil(sqrt(n));
        } else if (n >= 0) {
            int m1 = ceil(sqrt(n));
            int m2 = n - 1;
            int m3 = (n + 1) / 2;
            n = min(min(m1, m2), m3);
        } else {
            n -= m + 1;
            break;
        }
    }
    cout << n << endl;
}

int main(){
    int T; cin >> T;
    while (T -- ) solve();
    return 0;
}