先对原式进行化简：

$$\begin{aligned}X&=a^3+a^2b+ab^2+b^3\\&=a^2(a+b)+b^2(a+b)\\&=(a+b)(a^2+b^2)\end{aligned}$$

没啥用，只是方便写代码而已，完全可以不花简。

我们让 $a \le b$，可以得到当 $a=b$ 时 $a$ 最大，此时原式化简为 $4a^3$。而 $N \le 10^{18}$，$a=b=629961$ 时原式等于 $1000002262298522724$，大于 $10^{18}$，因此 $a$ 最大只会到 $629961$。

考虑枚举 $a$，明显 $a$ 固定时 $b$ 越大原式越大，具有单调性，可以二分 $b$。$a$ 最小为 $0$，$b=10^6$ 时原式刚好等于 $10^{18}$，因此二分 $b$ 时左边界为 $a-1$，右边界为 $10^6$。

最终时间复杂度为 $O(nlogn)$，其中$n=10^6$，可以通过。

还有一个小优化，如果枚举到当前 $a$ 时 $4a^3$ 已经大于等于 $ans$，就可以直接 $break$ 了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,ans;
bool check(int a,int b)
{
	return (a+b)*(a*a+b*b)>=n;
}
signed main()
{
	scanf("%lld",&n);ans=1e18;
	for(int a=0;a<=629961;a++)
	{
		if(4*a*a*a>=ans)break;
		int l=a-1,r=1e6,mid,b=1e6;
		while(l+1<r)
		{
			mid=(l+r)>>1;
			if(check(a,mid))r=mid,b=min(b,mid);
			else l=mid;
		}
		ans=min(ans,(a+b)*(a*a+b*b));
	}
	printf("%lld\n",ans);
	return 0;
}

然后其实可以根据 $n$ 来计算 $a$ 的最大值和二分 $b$ 时的右边界，进一步优化。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,ans;
bool check(int a,int b)
{
	return (a+b)*(a*a+b*b)>=n;
}
signed main()
{
	scanf("%lld",&n);
	int mxa=pow(n/4,1/3);
	while(mxa*mxa*mxa*4<n)mxa++; 
	ans=mxa*mxa*mxa*4;
	int mxb=pow(n,1/3);
	while(mxb*mxb*mxb<n)mxb++;
	for(int a=0;a<=mxa;a++)
	{
		if(4*a*a*a>=ans)break;
		int l=a-1,r=mxb,mid,b=mxb;
		while(l+1<r)
		{
			mid=(l+r)>>1;
			if(check(a,mid))r=mid,b=min(b,mid);
			else l=mid;
		}
		ans=min(ans,(a+b)*(a*a+b*b));
	}
	printf("%lld\n",ans);
	return 0;
}

题目大意

题目描述清楚，不做赘述

解题思路

定义 $f(a,b)=a^{3}+a^{2}b+ab^{2}+b^{3}$ ，则有：

$$f(a+1,b)-f(a,b)$$ $$=(a+1)^{3}+(a+1)^{2}b+(a+1)b^{2}+b^{3}-a^{3}+a^{2}b+ab^{2}+b^{3}$$$$=3a^{2}+(3+2b)a+(1+2b+b^{2})$$

题目要求 $a,b≥0$ ，所以 $f(a,b)$ 具有单调性，二分 $/$ 双指针都能过

$O(n^\frac{1}{3})$ 双指针代码 $:$

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int check(int a,int b){
	return (a*a+b*b)*(a+b);
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	
	int l=0,r=1e6;
	int ans=1e18;
	while(l<=r){
		if(check(l,r)>=n)ans=min(check(l,r),ans),r--;
		else l++;
	}
	cout<<ans<<'\n';
	
	return 0;
}

$O(n^\frac{1}{3}logn^\frac{1}{3})$ 二分代码 $：$

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int check(int a,int b){
	return (a*a+b*b)*(a+b);
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	int l=0,r=1e6;
	int k=0;
	while(l<=r){
		int mid=(l+r)>>1;
		if(mid*mid*mid>=n)k=mid,r=mid-1;
		else l=mid+1;
	}
	
	int ans=1e18;
	for(int i=0;i<=k;i++){
		int l=i,r=k;
		while(l<=r){
			int mid=(l+r)>>1;
			if(check(i,mid)>=n)ans=min(ans,check(i,mid)),r=mid-1;
			else l=mid+1;
		}
	}
	cout<<ans<<'\n';
	
	return 0;
}

ezkm

思路

首先因为$n\leq 10^{18}$,而题目的式子是三次的，不难发现要求的$a,b$肯定不会超过$1\times 10^6$。然后也不难发现如果$a$是固定的，原式的值随$b$的增大而增大，符合二分的条件。因此不妨枚举$a$的值，然后二分$b$的值，不断更新答案即可。

AC代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
	int n;scanf("%lld",&n);
	int l=0,r=1000000,sqr;
	while(l<=r)
	{
		int mid=l+r>>1;
		if(mid*mid*mid>=n)r=mid-1,sqr=mid;
		else l=mid+1;
	}
	int ans=1ll<<60;
	for(int i=0;i<=sqr;i++)
	{
		int l=i,r=sqr;
		while(l<=r)
		{
			int mid=l+r>>1;
			if(mid*mid*mid+i*i*i+i*i*mid+i*mid*mid>=n)r=mid-1,ans=min(ans,mid*mid*mid+i*i*i+i*i*mid+i*mid*mid);//一坨大的
			else l=mid+1;
		}
	}
	printf("%lld\n",ans);
	return 0;
}