题解 | 幂次进近

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            long n = sc.nextLong(), k = sc.nextLong();
            long l = 1, r = inf;
            while (l <= r) {
                long mid = (l + r) / 2;
                if (pow(mid, k) < n) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            System.out.println(n - pow(r, k) < pow(l, k) - n ? r : l);
        }
    }
    static long inf = Long.MAX_VALUE / 2;
    static long pow(long a, long b) {
        long res = 1;
        while (b > 0) {
            if (b % 2 == 1) {
                res = slowMul(res, a);
                if (res >= inf) {
                    return inf;
                }
            }
            b /= 2;
            a = slowMul(a, a);
        }
        return res;
    }
    static long slowMul(long a, long b) {
        long res = 0;
        while (b > 0) {
            if (b % 2 == 1) {
                res += a;
                if (res >= inf) {
                    return inf;
                }
            }
            b /= 2;
            a = Math.min(inf, a * 2);
        }
        return res;
    }
}

贴一个java版本的代码，这道题目很显然可以用二分来做，关键在于防溢出，可以使用快速幂加龟速乘，令inf=Long.MAX_VALUE / 2,在龟速乘过程中如果发现最终结果会超过inf就直接返回inf，快速幂中也同理。