题解 | 小数字

#include <iostream>
#include <cmath>
using namespace std;
// m的最大值是1e9，硬算必然超时
// 主要的思路是：n < 3开始，-1就是最优解
// 前面开方、除2实际上不会计算很多次
// n < 3后直接减掉剩余次数就是答案
int main() {
    int t;
    cin >> t;
    while(t--) {
        int n, m;
        cin >> n >> m;
        for(auto c = 0; c < m; c++) {
            if(n >= 7) {
                n = int(ceil(sqrt(double(n))));
            }
            else if(n >= 3) {
                if(n&1) {
                    n = (n >> 1) + 1;
                } else {
                    n = n >> 1;
                }
            } else {
                n = n - m + c;
                break;
            }
        }
        cout << n << endl;
    }
}
// 64 位输出请用 printf("%lld")