2010 哈尔滨网络预选赛 1003解题报告

这道题其实可以转化为开方一个很大的数。这道题由于是求x使得x*x <= n < (x+1)*(x+1)的值，那么其实我们n的平方根就是居于x和x+1之间，但是这道题只是求x的值，也就是说只需要求一个近似值。如果我们从1开始递增的去测试，这道题不用想肯定是超时的，那么我们怎么很快的估算个x的值的平方非常接近于n呢？

求一个大数的平方根，在网上有模板算法的！但是基本上都是c/c++的，而且基本上都是求的一个高精度（double或者BigDecimal）的值，这道题本身是不需要求小数点后面的精度的，所以这些算法不一定适合。

其实我们很容易发现一个数的平方根肯定是小于这个数的一半，一半一半于是我们可以想到二分求解，怎么二分个发呢？那么我就带大家看看我的二分法吧！呵呵。。。经过测试，AC时间比我在网上找到的快很多！

import java.io.*;
import java.math.*;
import java.util.*;


public class Main {

 /**
  * 自己想的二分求近似平方根
  * @param num
  * @return sqrt
  */
 private static BigInteger sqrt(BigInteger num) {
  BigInteger a = num.shiftRight(1);
  BigInteger b = a.add(BigInteger.ONE);
  BigInteger aa = a;
  boolean flag = false;
  
  while (true) {
   
   if (a.pow(2).compareTo(num) <= 0) {
    if (b.pow(2).compareTo(num) > 0) {
     return a;
    }
 
    a = a.add(aa);//当a+1 的平方任然小于num时，加上自身
    b = a.add(BigInteger.ONE);
    flag = true;
   } else {
    if (flag) {//当已经找到一个很接近num的平方根的时候，在加上本身的平方大于num，此时开始二分递减
     aa = aa.shiftRight(1);
     if (aa.compareTo(BigInteger.ZERO) == 0)
      aa = BigInteger.ONE;
     a = a.subtract(aa);
     b = a.add(BigInteger.ONE);
    } else {//最初是做二分整除
     a = a.shiftRight(1);
     b = a.add(BigInteger.ONE);
     aa = a;
    }
   }
  }

 }
/**
 * 网上找的，精确开平方根
 * @param num
 * @param mc
 * @return sqrt
 */
 public static BigDecimal sqrt(BigDecimal num, MathContext mc) {
  if (num.compareTo(BigDecimal.ZERO) < 0)
   throw new ArithmeticException("sqrt with negative");
  int precision = mc.getPrecision();
  RoundingMode rm = mc.getRoundingMode();
  int p = num.precision();
  int s = num.scale();
  int n = p - s;
  n = n % 2 == 0 ? n - 2 : n - 1;
  final BigDecimal base = num.scaleByPowerOfTen(-n);
  if (base.scale() > precision * 2 + 2)
   base.setScale(precision * 2 + 2, rm);
  BigDecimal radix = BigDecimal.ZERO;
  for (int i = 0; i < precision + 1; i++) {
   if (radix.pow(2).equals(base)) {
    break;
   } else {
    for (int j = 0; j < 10; j++) {
     radix = radix.add(BigDecimal.ONE.scaleByPowerOfTen(-i));
     int compare = base.compareTo(radix.pow(2));
     if (compare <= 0)
      break;
    }
    if (radix.pow(2).equals(base))
     break;
    radix = radix.subtract(BigDecimal.ONE.scaleByPowerOfTen(-i));
   }
  }
  radix = radix.scaleByPowerOfTen(n / 2);
  // System.out.println(radix);
  return radix.abs(mc);
 }

 public static void main(String[] args) {
  /*
   * StringBuilder sb = new StringBuilder(); sb.append(1); for (int i = 1;
   * i < 200; i++) { sb.append(0); } long cur1 =
   * System.currentTimeMillis(); BigDecimal n = new
   * BigDecimal(sb.toString()); BigDecimal sq = sqrt(n, new
   * MathContext(150)); String s = sq.toString(); int index =
   * s.indexOf("."); index = index > -1 ? index : s.length(); BigInteger b
   * = new BigInteger(s.substring(0, index));
   * System.out.println(b.toString(2)); long cur2 =
   * System.currentTimeMillis(); System.out.println(cur2 - cur1);
   * BigInteger sqr = sqrt(new BigInteger(sb.toString()));
   * System.out.println(sqr.toString(2)); long cur3 =
   * System.currentTimeMillis(); System.out.println(cur3 - cur2);
   */
  Scanner sc = new Scanner(System.in);

  while (sc.hasNext()) {
   String str = sc.nextLine();
   if (str.equals("#"))
    break;

   // BigDecimal n = new BigDecimal(str);
   // BigDecimal sq = sqrt(n, new MathContext(150));
   // String s = sq.toString();
   // int index = s.indexOf(".");
   // index = index > -1 ? index : s.length();
   // BigInteger b = new BigInteger(s.substring(0, index));
   // System.out.println(b.toString(2));
   BigInteger nn = new BigInteger(str);
   if (nn.compareTo(BigInteger.ZERO) == 0)
    System.out.println(0);
   else if (nn.compareTo(BigInteger.ONE) == 0)
    System.out.println(1);
   else {
    BigInteger sqrr = sqrt(nn);
    System.out.println(sqrr.toString(2));
   }
  }
 }
}

//网上找的800+msAC，二分法400+msAC！