题解 | 幂次进近

#include <bits/stdc++.h>
using namespace std;
const int N=3e5+10;
const int mod = 998244353;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
const ll INF = (ll)2e18;

ll n,k;

static inline i128 abs128(i128 x){
    return x < 0 ? -x : x;
}

i128 qpow(i128 a,i128 b)
{
   
    i128 res = 1;
 
    if (a > (i128)INF) return (i128)INF;

    while(b > 0)
    {
        if(b & 1)
        {
           
            if (a != 0 && res > (i128)INF / a) return (i128)INF;
            res = res * a;
            if(res > (i128)INF) return (i128)INF;
        }
        b >>= 1;
        if(b == 0) break;

        if (a != 0 && a > (i128)INF / a) a = (i128)INF;
        else a = a * a;

        if(a > (i128)INF) a = (i128)INF;
        if(res > (i128)INF) return (i128)INF;
    }
    return res;
}

bool check(ll x)
{
    i128 res = qpow((i128)x, (i128)k);
    return res <= (i128)n;
}

void solve()
{
    cin>>n>>k;


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

    i128 l = 1;
    i128 r = (i128)n;               
    i128 res = 1;

    while(l<=r)
    {
        i128 mid = (l+r)/2;
        if(check((ll)mid))
        {
            res = mid;
            l = mid+1;
        }
        else
        {
            r = mid - 1;
        }
    }

    i128 res1 = qpow(res,(i128)k);
    i128 res2 = qpow(res+1,(i128)k);

    if(abs128(res1-(i128)n) <= abs128(res2-(i128)n))
    {
        // 输出 i128
        long long out = (long long)res;
        cout<<out<<'\n';
    }
    else {
        long long out = (long long)(res+1);
        cout<<out<<'\n';
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

这题太容易爆了，换i128才过的