ABC246D 2-variable Function Solution

更好的阅读体验戳此进入

题面

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

Solution

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

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

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

Code

xxxxxxxxxx
59
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

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

11
using namespace std;
12
using namespace __gnu_pbds;
13

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

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

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

26
ll Func(int a, int b){return (ll)a * a * a + (ll)a * a * b + (ll) a * b * b + (ll)b * b * b;}
27
int main(){
28
    ll N = read<ll>();
29
    ll mn(LLONG_MAX);
30
    for(int x = 0; x <= (int)1e6; ++x){
31
        int l = 0, r = (int)1e6;
32
        ll cur(-1);
33
        while(l <= r){
34
            int mid = (l + r) >> 1;
35
            ll tmp = Func(x, mid);
36
            if(tmp >= N)cur = tmp, r = mid - 1;
37
            else l = mid + 1;
38
        }
39
        mn = min(mn, cur);
40
    }printf("%lld\n", mn);
41
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
42
    return 0;
43
}
44

45
template<typename T>
46
inline T read(void){
47
    T ret(0);
48
    short flag(1);
49
    char c = getchar();
50
    while(c != '-' && !isdigit(c))c = getchar();
51
    if(c == '-')flag = -1, c = getchar();
52
    while(isdigit(c)){
53
        ret *= 10;
54
        ret += int(c - '0');
55
        c = getchar();
56
    }
57
    ret *= flag;
58
    return ret;
59
}

UPD

update-2022_10_21 初稿