ABC246D 2-variable Function Solution

• ABC246D 2-variable Function Solution
  • 更好的阅读体验戳此进入
  • 题面
  • Solution
  • Code
  • UPD

更好的阅读体验戳此进入

题面

存在函数 $ f(a, b) = a^3 + a^2b + ab^2 + b^3 $，要求 $ a, b \ge 0 $，给定 $ n $，求最小的 $ f(a, b) $ 满足 $ f(a, b) \ge n \(。\) n \le 10^{18} $。

Solution

显然 $ a, b $ 的范围不超过 $ 10^6 $，则可以枚举 $ a $，二分 $ b $，取最小值即可。

对于二分 $ b $ 的单调性证明，可以考虑固定 $ a $ 为参数，则有函数 $ f(b) = b^3 + ab^2 + a^2b + a^3 $，三次函数不好操作，所以考虑求导，显然 $ f'(b) = 3b^2 + 2ab + a^2 $，因为 $ a, b $ 非负，所以显然导函数 $ f'(b) \ge 0 $，所以范围内函数取值单调递增，于是可以二分。

或者不进行二分，根据单调性，显然 $ a $ 减小时 $ b $ 不会比上次更大，所以写个双指针枚举，$ a $ 升序，$ b $ 降序，小于 $ n $ 时直接 break 即可。

Code

#define _USE_MATH_DEFINES
#include <bits/extc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}

using namespace std;
using namespace __gnu_pbds;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

template<typename T = int>
inline T read(void);

ll Func(int a, int b){return (ll)a * a * a + (ll)a * a * b + (ll) a * b * b + (ll)b * b * b;}
int main(){
    ll N = read<ll>();
    ll mn(LLONG_MAX);
    for(int x = 0; x <= (int)1e6; ++x){
        int l = 0, r = (int)1e6;
        ll cur(-1);
        while(l <= r){
            int mid = (l + r) >> 1;
            ll tmp = Func(x, mid);
            if(tmp >= N)cur = tmp, r = mid - 1;
            else l = mid + 1;
        }
        mn = min(mn, cur);
    }printf("%lld\n", mn);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template<typename T>
inline T read(void){
    T ret(0);
    short flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

UPD

update-2022_10_21 初稿