URAL 1153. Supercomputer 二分求根

28

7

题意

给你1-n个数的和，求出n多大。

做法：

根据等差数列公式， 得 (1+n)*n/2 =(n^2+n)/2;

设给的和 为ans。

n^2+n-2ans=0

然后根据 公式 （-b+根号（b^2-4ab））/2a  就可以算出n是多少了。
因为ans很大，所以要用大数。java大数也没有现成的开根号函数，所以要用二分来求 根。

import java.math.*;
import java.util.*;
import java.io.*;
 
public class Main{ 
	
	static BigInteger li=BigInteger.ZERO;
    static BigInteger yi=BigInteger.ONE;
    static BigInteger er=BigInteger.valueOf(2);
	public static BigInteger sqrtt(BigInteger n)
	{
		BigInteger l=yi,r=n,mid;
		while(l.compareTo(r)<=0)
		{
			mid=l.add(r).divide(er);
			
			if(mid.multiply(mid).compareTo(n)<0)
				l=mid.add(yi);
			else
				r=mid.subtract(yi);
			//System.out.println(l+" "+r);
		}
		return l;
	}
	
        public static void main(String[] args)
       {
                 Scanner input = new Scanner(System.in);

                 BigInteger a;
                  
                 while(input.hasNext())
                 {
                	 a=input.nextBigInteger(); 
                	 a=a.multiply(BigInteger.valueOf(8)); 
                	 a=a.add(BigInteger.ONE); 
                	 a=sqrtt(a); 
                	 System.out.println(a.subtract(BigInteger.ONE).divide(BigInteger.valueOf(2))); 
                 } 
       } 
}

URAL 1153. Supercomputer 二分求根

原文：http://blog.csdn.net/u013532224/article/details/44571661