题解 | #幂次进近# | C++版本且无int128，顶级整数溢出防御

题目描述

给定正整数 和 ，求一个正整数 ，使得 最小。若存在多个 使得差值相同，输出任意一个即可（通常取较小者，但本题数据保证唯一最优或按实现逻辑可过）。

本题是考察整数快速幂 + 二分搜索 + 溢出防御的题，难度中等偏上

核心思路

核心观察

• 函数 在 时是单峰函数：先递减后递增。
• 最优解 必然在 附近，即满足 的两个候选值 和 中产生。
• 由于 ，当 时， 的上界很小（如 时 ， 时 ），可安全二分。
• 关键难点：计算 时极易发生 long long 溢出，导致未定义行为（如负数、0），进而引发除零错误（SIGFPE）或逻辑错误。

本题快速幂不让取模，所以溢出风险只能一层层防御。

算法步骤

1. 特判边界：
   • 若 ，直接输出 。
   • 若 ，由于 ，最优解必为 。
2. 设置合理二分上界：
   • 使用浮点开方估算：r = pow(1e18, 1.0 / k)，并隐式限制范围。
3. 二分查找最大 满足 ：
   • 使用带溢出防御的快速幂 qpow(a, b, n)：
     • 若底数 a <= 0（溢出标志），立即返回哨兵值 2*n。
     • 若乘法会溢出（ans > 2*n / a），返回 2*n。
   • 通过比较 qpow(mid, k, n) <= n 调整二分边界。
4. 暴力比较候选解：
   • 计算 和 的真实幂值（此时 很小，无溢出风险）。
   • 比较差值 与 ，输出更优者。

正确性分析

• 二分正确性：快速幂虽可能返回截断值 2*n，但只要保证“”的判断符号正确（即真实值 时返回 ，否则返回 ），二分就能收敛到正确区间。
• 溢出防御：a <= 0 利用 C++ 短路求值，避免除零；哨兵值 2*n 确保二分方向正确。
• 最终比较精确：因 极小（如 时 ）， 和 可精确计算，比较无误差。

复杂度分析

• 时间复杂度：
  • 其中 为测试用例数， 为二分上界（ 时 ， 时 ）。
  • 每次快速幂耗时 ，二分耗时 。
• 空间复杂度：
  • 仅使用常数额外空间。

#include <bits/stdc++.h>
using namespace std;
#define int long long

inline int qpow(int a, int b, int n) {
    if (a <= 1) return a;
    int ans = 1;
    while (b) {
        if (b & 1) {
          	//三级防御：底数a溢出防御以及ans溢出防御
            if (a<=0||ans > 2*n / a) return 2*n;//只有进行本次运算才溢出判断
            ans = (ans * a);
        }
        a *= a;//这里溢出判断会丢解
        b >>= 1;
    }
    return ans;
}


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        if (k > 60) {//一级防御，60次幂往上可以直接吃席了，不用算了
            cout << 1 << endl;
            continue;
        }
        if(k==1){//小加速特判
            cout<<n<<endl;
            continue;
        }
        int l = 1, r = pow(1e18, 1.0 / k);//二级防御：设置合理上界
        int tem = 0;
        while (l <= r) {
            int mid = (l + r) >> 1;
            tem = qpow(mid, k, n);
            if (tem <= n) {
                l = mid + 1;
            } else r = mid - 1;
        }

        if (qpow(r + 1, k, n) - n < n - qpow(r, k, n))cout << r + 1 << endl;//r+1容易溢出
        else cout << r << endl;
    }
}

不建议你修改哨兵数值大小以及溢出判断位置