SDUT1401

大整数

题目描述

一个k（1<=k<=80）位的十进制正整数n，我们称其为大整数。

现在的问题是，请你设计一个程序，对于给出的某一个大整数n，找到满足条件p 3+p 2+3p<=n的最大值。

输入

输入数据只有一行，是一个k位的大整数n。行首行末无多余空格。

输出

输出你所找到的p的最大值。行首行末无多余空格。

示例输入

1000000000000001000000000000003000000000000001

示例输出

import java.math.*;

import java.util.*;

public class Main {

static BigInteger num;

public BigInteger bSearch(BigInteger k)

{

BigInteger mid,left=BigInteger.valueOf(0),right=k;

BigInteger one=BigInteger.valueOf(1);

BigInteger two=BigInteger.valueOf(2);

BigInteger three=BigInteger.valueOf(3);

BigInteger temp;

while(left.compareTo(right)<=0)

{

mid=(left.add(right).divide(two));

temp=mid.pow(3).add(mid.pow(2)).add(mid.multiply(three));

if(temp.compareTo(k)>0) right=mid.subtract(one);

else left=mid.add(one);

}

return right;

}

public static void main(String[] args) {

Scanner cin = new Scanner(System.in);

while(cin.hasNext())

{

num=cin.nextBigInteger();

Main t=new Main();

BigInteger ans=t.bSearch(num);

System.out.println(ans);

}

}

}