二分 + 饱和乘法 题解 | #幂次进近#

学到个玩意叫饱和乘法

#include <bits/stdc++.h>

#define x first
#define y second
#define all(x) x.begin(), x.end()

using namespace std;
using i128 = __int128;
using u128 = unsigned __int128;

typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int N = 1e5 + 10;
const int INF = 1e9;
const LL LL_INF = 1e18;
const LD EPS = 1e-8;
const int dx4[] = {-1, 0, 1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};

istream &operator>>(istream &is, i128 &val) {
    string str;
    is >> str;
    val = 0;
    bool flag = false;
    if (str[0] == '-') flag = true, str = str.substr(1);
    for (char &c: str) val = val * 10 + c - '0';
    if (flag) val = -val;
    return is;
}

ostream &operator<<(ostream &os, i128 val) {
    if (val < 0) os << "-", val = -val;
    if (val > 9) os << val / 10;
    os << static_cast<char>(val % 10 + '0');
    return os;
}

i128 safe_pow(i128 a, i128 b, i128 t) {
    if (b == 0) return 1;
    if (a == 1) return 1;
    if (a == 0) return 0;

    if (b > 128 && a >= 2) return t + 1; 

    i128 res = 1;
    for (int i = 0; i < (long long)b; i++) {
        if (res > t / a) return t + 1;
        res *= a;
    }
    return res;
}

void solve() {
    i128 n, k;
    cin >> n >> k;
    auto check = [&](i128 mid) {
        return safe_pow(mid, k, 4e18);
    };

    if (k == 1) {
        cout << n << '\n';
        return;
    }

    i128 l = 1, r = 2e9;
    while (l < r) {
        i128 mid = l + r + 1 >> 1;
        if (check(mid) > n) r = mid - 1;
        else l = mid;
    }
    i128 a = l;

    l = 1, r = 2e9;
    while (l < r) {
        i128 mid = l + r >> 1;
        if (check(mid) >= n) r = mid;
        else l = mid + 1;
    }
    i128 b = l;

    i128 x = safe_pow(a, k, 4e18);
    i128 y = safe_pow(b, k, 4e18);

    i128 ans1 = n >= x ? n - x : x - n;
    i128 ans2 = y >= n ? y - n : n - y;
    if (ans1 <= ans2) cout << a << '\n';
    else cout << b << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T;
    cin >> T;
    while (T--) solve();
    cout << fixed << setprecision(15);

    return 0;
}