题解 | 幂次进近

//算法练习No.9
//数学构造+边界处理
#include <iostream>
#include <cmath>
using namespace std;

typedef __int128_t int128;

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

    if(k == 1)
    {
        cout << n << endl;//m=n,结果为0
        return;
    }

    if(k >= 62)
    {
        cout << 1 << endl;//
        return;
    }

    //不大不小的情况
    long long m = pow(n,1.0/k);//m == n^1/k
    if(m == 0) m = 1;
    //比较m^k 与 m+1^k
    int128 a {1};
    int128 b {1};
    for(int i = 0;i<k;i++) a *= m;
    for(int i = 0;i<k;i++) b *= (m+1);
    //int128 不能直接用 abs
    int128 c = (a>(int128)n)?(a-n):(n-a);
    int128 d = (b>(int128)n)?(b-n):(n-b);

    if(c > d)
    {
        cout << m+1 << endl;
    }
    else
    {
        cout << m << endl;
    }


}

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

    int t;
    cin >> t;
    while(t--)
    {
        solve();
    }
   
    return 0;
}
// 64 位输出请用 printf("%lld")