Given an integer $N$, find the smallest integer $X$ that satisfies all of the conditions below.Problem Statement
Constraints
Input
Input is given from Standard Input in the following format:
$N$
Output
Print the answer as an integer.
Sample Input 1
9
Sample Output 1
15
For any integer $X$ such that $9 \le X \le 14$, there is no $(a, b)$ that satisfies the condition in the statement.
For $X=15$, $(a,b)=(2,1)$ satisfies the condition.
Sample Input 2
0
Sample Output 2
0
$N$ itself may satisfy the condition.
Sample Input 3
999999999989449206
Sample Output 3
1000000000000000000
Input and output may not fit into a $32$-bit integer type.
\(a^3+a^2b+ab^2+b^3=(a+b)^3-2ab(a+b)\)
我们不妨枚举 \(a+b\) 为多少，\((a+b)^3\) 是 \(\theta(n^{\frac{1}{3}})\) 级别的。可以直接枚举。
我们现在知道了 (a+b)，那么我们需要找到是否有 一组 \((a,b)\) 满足上面那个等式。因为和已经确定了，那么剩下的是一个二次函数，具有单调性。我们可以二分 \(a\)，求出 \(b\)，找到最接近的那个解就行了。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,ans=2e18,l,r,md;
int main()
{
scanf("%lld",&n);
for(LL i=0;i<=2000005;i++)
{
if(i*i*i<n)
continue;
l=0,r=i/2;
while(l<=r)
{
md=l+r>>1;
if(i*i*i-2*md*(i-md)*i>=n)
l=md+1;
else
r=md-1;
}
if(i*i*i-2*r*(i-r)*i>=n)
ans=min(ans,i*i*i-2*r*(i-r)*i);
}
printf("%lld",ans);
}