题目

人总要有些秘密。一天上课的时候，小J无意间瞥见小R在聊天窗中发送着一串又一串的数字。 整节课小J都在观察小R，终于发现了一个奇怪的式子 6×x3+2×x2-x， 猜测这可能与小R发出的数字有关系。

小J只拿到了加密后的数字 n，现在需要找到加密前小R的秘密 x 到底是什么。

输入：1 个整数 n，表示经由 6×x3+2×x2-x 加密后的值。数据保证 x 存在正整数解。
输出：1 个整数 x。
数据范围：50% 的数据 n ≤ 109；100% 的数据 n ≤ 1013。

样例：
输入 6190 → 输出 10  |  输入 11288500567455 → 输出 12345

思路

f(x) = 6x3+2x2-x 对正整数 x 严格单调递增， 因此可以直接对 x 做二分查找， 不需要求解三次方程。

设搜索范围 [1, 2000000]，每次取中点 mid，计算 f(mid) 与 n 的大小关系， 缩小区间直到找到精确解。

C++ · p39.cpp 
#include<bits/stdc++.h>
using namespace std;

int main(){
    long long n;
    scanf("%lld", &n);
    long long lo = 1, hi = 2000000;    // x 的搜索范围上界
    while(lo < hi){
        long long mid = (lo + hi) / 2;
        long long f = 6*mid*mid*mid + 2*mid*mid - mid;    // f(x) = 6x³+2x²-x
        if(f < n) lo = mid + 1;
        else if(f > n) hi = mid - 1;
        else { printf("%lld\n", mid); return 0; }
    }
    printf("%lld\n", lo);
    return 0;
}

复杂度分析

  • 时间复杂度：O(log N)，N = 2×106，约 21 次迭代。
  • 空间复杂度：O(1)。
今日感受

看到 f(x) = 6x3+2x2-x，第一反应想用 cbrt() 凑解析解，但这个式子根本化不开。 转念一想：f 单调递增，直接二分就行，完全不需要数学。
看到幂次和10的13次方，一定用 long long。

← 返回菜鸟的coding