“Sgu/111”的版本间的差异

2015年2月19日 (四) 20:02的最后版本

摘要

（AC 1817）

题意

高精度开方。

题解

这一题和CodeVS/3119是相同的，可是那题的代码莫名其妙PE了……我也不造为什么，也许是io流的问题，不想研究了。不过，高精度神魔的听说java有大整数/小数类，于是顺手开了个java的小坑。之前配置过Android环境了，环境也就不多提了。入个门，写个二分的高精度开方也不算太难的事了。

Java的a+b程序

先来个sgu官方java的a+b

//引用相关库//
import java.util.*;
import java.io.*;
//主程序类：Solution//
public class Solution 
{
  //主程序，参数是String[] arg//
  public static void main (String[] argv) throws IOException
  {
    //创建一个类似于cin的流//
    BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    //读入一行//
    StringTokenizer st = new StringTokenizer(cin.readLine());
    //从一行中解析//
    int a = Integer.parseInt(st.nextToken());
    int b = Integer.parseInt(st.nextToken());
    int c = a + b;
    //输出//
    System.out.println(c);
  }
}

Java的输入输出

首先先调教输入输出，java中输出常见有几种：

System.out.print(); //cout<<...;//
System.out.println(); //cout<<...<<endl;//
System.out.printf(); //printf(...);注意换行用%n表示//

输入先要创建一个流：

Scanner cin = new Scanner(System.in); 

或者

Scanner cin = new Scanner(new BufferedInputStream(System.in));//据说会更快一点//

然后进行输入：

变量=cin.next类型名();

如

a=cin.nextInt();

但是听说这种cin就和C++的cin一样容易超时，如果想要快应该用StreamTokenizer和PrintWriter，不过由于我只是用用高精度就无所谓这个了，有兴趣请阅读http://blog.csdn.net/mingchaoyan/article/details/6301858。

Java的数据类型

常见的有：int,double,boolean,String,BigDecimal（高精度浮点数）,BigInteger（高精度整数），注意区分大小写。

Java的高精度和进制转换

居然没有重载运算符，差评！

用法大概这几种：

c=a.add(b);//c=a+b;//
c=a.subtract(b);//c=a-b;//
c=a.multiply(b);//c=a*b;//
c=a.divide(b);//c=a/b;//
c=a.mod(b);//c=a%b;//
a.compareTo(b);//a和b:相等返回0,小于返回-1,大于返回1//
c=a.pow(n);//c=a^n;//
str=a.toString();//对应十进制字符串//
str=a.toString(n);//对应n进制字符串//
a=valueOf(n);//a=(int)n;//
c=a.gcd(b);//abs(a)和abs(b)的最大公约数//
c=a.abs();//c=abs(a);//
i=a.hashCode();//a的哈希码//
p=a.isProbablePrime(int certainty);//是否可能为素数（估计）//
c=a.nextProbablePrime();//大于a的可能为素数的第一个整数//
p=a.signum();//正负号函数//
c=BigInteger.ZERO;//c=0;//
c=BigInteger.ONE;//c=1;//
c=BigInteger.TEN;//c=10;//
c=new BigInteger(st, base);//通过base进制的字符串st构造高精度整数//
st=Integer.toString(num, base);//把10进制的数num转成base进制的st(base <= 35)//
i=Integer.parseInt(st, base); //把base进制的st，转成10进制的int//

代码

import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Solution{
    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        BigInteger N, l, r, mid;
        N = cin.nextBigInteger();
        l = BigInteger.ZERO;
        r = N.abs().add(BigInteger.ONE);
        while (l.compareTo(r) <= 0) {
            mid = l.add(r).divide(BigInteger.valueOf(2));
            if (mid.multiply(mid).compareTo(N) >= 0) 
                r = mid.subtract(BigInteger.ONE);
            else
                l = mid.add(BigInteger.ONE);
        }
        while (l.multiply(l).compareTo(N) > 0) {
            l = l.subtract(BigInteger.ONE);
        }
        System.out.println(l);
    }
}

参考资料和拓展阅读