【題解】Luogu P1601 【A+B Problem(高精)】

看到好像没有Java的题解(不调用Math库中的BigInteger的情况下),那就水一发(巨长400行,适用于高精加减乘除)(当然这个数据卡点请忽略那个if-else(原因超过String类的默认内存大小))

import java.util.Scanner;

class BigInteger {
    public static final BigInteger ZERO = new BigInteger();  
    public static final BigInteger ONE = new BigInteger("1");  
    public static final BigInteger TWO = new BigInteger("2");  

    /*
     * 这样有利于解决正负数问题,所有大整数在操作时可以直接对value进行,最后统一考虑得到结果的符号。
     */
    private String value;//字符串value为该大整数的绝对值
    private int length;//length存储该绝对值的位数
    private boolean positiveorNegative;//positiveor negative. + is true, - is false

    /*
     * 无参数构造函数BigInteger()
     */
    BigInteger(){
        this.length = 1;
        this.positiveorNegative = true;
        this.value = "";
    }

    /*
     * 带有字符串的构造函数BigInteger(String s)
     * 通过私有方法isLegal(s)对参数进行合法性判断;
     * 判断该字符串是否带有符号,设置其符号positiveorNegative;
     * 通过私有方法findStartPos(s)寻找字符串真正有意义的最高位;
     * 将最高位之后的所有字符存入value中,并在length中记录该value的长度;
     *  对0做特殊处理。
     */
    BigInteger(String s){
        if(isLegal(s)) {
            if(s.charAt(0) == '+' || s.charAt(0) == '-') {
                this.positiveorNegative = s.charAt(0) == '+' ? true:false;
            }else {
                this.length = s.length();
                this.positiveorNegative = true;
            }

            int sp = findStartPos(s);

            this.value = s.substring(sp);
            this.length = s.length() - sp;

            if(this.value.charAt(0) == '0') {
                this.positiveorNegative = true;
                this.length = 1;
                this.value = "0";
            }
        }else {
            System.out.println("Unacceptable number!!!");
        }
    }

    /*
     * BigInteger转字符串publicString toString()
     * 由于数据结构中将符号位与数据位分离,所以在输出时只需要考虑在符号位pn==false时在value前加上负号即可。
     */
    public String toString() {
        if(positiveorNegative == false) {
            return "-" + value;
        }
        return value;
    }

    /*
     *  大整数比较是否相等public boolean equals(BigInteger x)
     *  与toString()类似,比较两个大整数的符号位和数据位是否相等即可。需要注意的是在数据位比较时要用equals(),直接使用等号比较的是引用的值而非真实数据。
     */
    public boolean equals(BigInteger x) {
        if(this.positiveorNegative == x.positiveorNegative && this.length == x.length && this.value.equals(x.value)) {
            return true;
        }
        return false;
    }

    /*
     *  大整数比较大小public int compare(BigInteger x)
     *  大于返回1,等于返回0,小于返回-1.
     *  直接通过符号位pn不同时比较两个数的大小;
     *  符号相同时,借助长度不同比较两个数的大小,正数长度大的大,负数长度小的大;
     *  符号长度都相同时,借助compareTo比较两个数的value,正数返回compareTo的结果对应点1和-1,负数返回compareTo结果的相反数的-1和1。
     */
    public int compare(BigInteger x) {
        if(this.positiveorNegative != x.positiveorNegative) {
            return this.positiveorNegative == true ? 1: -1;
        }

        if(this.length != x.length) {
            if(this.positiveorNegative) {
                return this.length > x.length ? 1 : -1;
            }else {
                return this.length < x.length ? 1 : -1;
            }
        }

        int tmp = this.value.compareTo(x.value);
        if(this.positiveorNegative) {
            tmp *= -1;
        }
        if(tmp > 0) {
            return -1;
        }
        if(tmp < 0) {
            return 1;
        }

        return tmp;
    }

    /*
     * 大整数加法public BigInteger add(BigInteger x)
     * 对于加法操作,只考虑符号位相同的情况,将符号位不同的情况丢给减法。
     * 对0做特殊处理,返回另一个数,注意是创建一个新的大整数进行返回,如new BigInteger(this.toString());
     * 如果两个数符号位不同,则创建x的备份xx,并使用私有方法changePN()改变xx的符号位,计算this-xx,将结果返回;
     * 创建两个字符串bigger和smaller,分别记录数据位较大的数据位和较小数的数据位;
     * 模拟加法操作:用bigger和smaller从最低位按位进行加法操作,借助私有方法charAdd()按位加,结果记录在字符串ans中;并通过carryValue来记录当前按位加结果是否得到进位,如果有进位,则在下一位加法操作时需要将carryValue加入按位加操作中,否则将其清零;
     * ans[i] =bigger[bigger.length-i]+smaller[smaller.length-i]+carryValue
     * 当smaller的最高位加完后,需要对bigger多出的高位继续与carryValue进行按位加;
     * 判断最高位是否产生进位,如果产生则补充一个最高位1;
     * 将ans进行反转操作,用其构造大整数,并将其符号位置为this的符号位。
     */
    public BigInteger add(BigInteger x) {
        if(x.value.equals("0")) {
            return new BigInteger(this.toString());
        }

        if(this.value.equals("0")) {
            return new BigInteger(x.toString());
        }

        if(this.positiveorNegative != x.positiveorNegative) {
            BigInteger xx = new BigInteger(x.toString());
            xx.changePN();
            return this.substract(xx);
        }

        String bigger,smaller;
        if((this.compare(x) >= 0 && this.positiveorNegative) || (this.compare(x) < 0 && !this.positiveorNegative)) {
            bigger = new String(this.value);
            smaller = new String(x.value);
        }else {
            bigger = new String(x.value);
            smaller = new String(this.value);
        }

        String tmpAns = new String();
        int carryValue = 0;
        for(int i = 1;i <= smaller.length();i++) {
            int tmpAdd = charAdd(bigger.charAt(bigger.length() - i),smaller.charAt(smaller.length() - i)) + carryValue;
            carryValue = tmpAdd >= 10 ? 1 : 0;
            tmpAns += String.valueOf(tmpAdd - carryValue * 10);
        }

        int pos = bigger.length() - smaller.length() - 1;
        while(carryValue != 0 && pos >= 0) {
            int tmpAdd = charAdd(bigger.charAt(bigger.charAt(pos)),'1');
            carryValue = tmpAdd >= 10 ? 1 : 0;
            tmpAns += String.valueOf(tmpAdd - carryValue * 10);
            pos--;
        }

        String ans = new String();
        tmpAns = reverse(tmpAns);

        if (carryValue == 0) {  
            ans = bigger.substring(0, Math.max(pos+1, 0))+tmpAns;  
        }else if (pos < 0) {  
            ans = "1" + tmpAns;  
        }  
        if (!this.positiveorNegative) {  
            ans = "-" + ans;  
        }  
        return new BigInteger(ans);  
    }

    /*
     * 大整数减法操作public BigInteger substract(BigInteger x)
     * 类似加法,只考虑符号位相同的情况,将符号位不同的情况丢给加法;接下来只介绍模拟减法的操作。
     * tmpSub= charSub(bigger[bigger.length()-i], smaller[smaller.length()-i], carryValue);
     */
    public BigInteger substract(BigInteger x) {  
        if (x.value.equals("0")) {  
            return new BigInteger(this.toString());  
        }else if (this.value.equals("0")) {  
            BigInteger ans = new BigInteger(x.toString());  
            ans.changePN();  
            return ans;  
        }  
        if (this.positiveorNegative != x.positiveorNegative) {  
            BigInteger xx = new BigInteger(x.toString());  
            xx.changePN();  
            return this.add(xx);  
        }  
        String bigger, smaller;  
        boolean tag = this.compare(x) >= 0 ? true : false;  
        if ((this.compare(x) >= 0 && this.positiveorNegative) || (this.compare(x) <= 0 && !this.positiveorNegative)) {  
            bigger = new String(this.value);  
            smaller = new String(x.value);  
        }else {  
            bigger = new String(x.value);  
            smaller = new String(this.value);  
        }  
        String tmpAns = new String();  
        int carryValue = 0;  
        for (int i = 1; i <= smaller.length(); i++) {  
            int tmpAdd = charSub(bigger.charAt(bigger.length() - i), smaller.charAt(smaller.length() - i), carryValue);  
            carryValue = tmpAdd < 0 ? 1 : 0;  
            if (tmpAdd == -100) {  
                carryValue = 1;  
                tmpAdd = 0;  
            }  
            tmpAns += String.valueOf(Math.abs(tmpAdd));  
        }  
        int pos = bigger.length() - smaller.length() - 1;  
        while(carryValue != 0 && pos >= 0) {  
            int tmpAdd = charSub(bigger.charAt(pos), '0', carryValue);  
            carryValue = tmpAdd < 0 ? 1 : 0;  
            tmpAns += String.valueOf(Math.abs(tmpAdd));  
            pos--;  
        }  
        String ansStr = new String();  
        tmpAns = reverse(tmpAns);  
        if (carryValue == 0) {  
            ansStr = bigger.substring(0, Math.max(pos+1, 0))+tmpAns;  
        }  
        BigInteger ans = new BigInteger(ansStr);  
        ans.positiveorNegative = tag;  
        return ans;
    }

    /*
     * 大整数乘法操作public BigInt multiply(BigInt x)
     * 采用分治的思想,设两个数分别为M1, M2,长度为均为l。可将其表示为:
     * M1 = AB,A为前l/2长度的数据位,B为后l-l/2长度的数据位;
     * M2 = CD,C为前l/2长度的数据位,D为后l-l/2长度的数据位;
     * 于是M1*M2可表示为
     * M1*M2 = A*C*(10^((l-l/2)*2)) + B*D + ((A-B)*(D-C)+A*C+B*D) *(10^(l-l/2))
     * 但是无法保证两个数数据位长度均为l,故需要将数据位短的前面补零补齐l位。之所以采取这样的方法是因为原本的乘法操作分解之后仍为四次乘法,而采取上式得乘法操作分解之后只需三次乘法操作,时间复杂度降为O(l^log(3))。
     */
    public BigInteger multiply(BigInteger x) {  
        if (x.value.equals("0") || this.value.equals("0")) {  
            return new BigInteger();  
        }  
        boolean ansPN = !(this.positiveorNegative ^ x.positiveorNegative);  
        if (x.length == 1 && this.length == 1) {  
            int ians = Integer.parseInt(x.value)*Integer.parseInt(this.value);  
            BigInteger ans = new BigInteger(String.valueOf(ians));  
            ans.setPN(ansPN);  
            return ans;  
        }  
        String a = this.value, b = x.value;  
        /**********Unify Length**********/  
        int len1 = Math.max(a.length(), b.length())-a.length();  
        int len2 = Math.max(a.length(), b.length())-b.length();  
        for (int i = 0; i < len1; i++) {  
            a = "0" + a;  
        }  
        for (int i = 0; i < len2; i++) {  
            b = "0" + b;  
        }  
        BigInteger a1 = new BigInteger(a.substring(0, a.length()/2));  
        BigInteger a2 = new BigInteger(a.substring(a.length()/2));  
        BigInteger b1 = new BigInteger(b.substring(0, b.length()/2));  
        BigInteger b2 = new BigInteger(b.substring(b.length()/2));  
        BigInteger ans1 = a1.multiply(b1);//a1*b1  
        BigInteger ans2 = a2.multiply(b2);//a2*b2  
        BigInteger sub1 = a1.substract(a2);  
        BigInteger sub2 = b2.substract(b1);  
        BigInteger ans3 = sub1.multiply(sub2);//(a1-a2)(b2-b1)  
        ans3 = ans3.add(ans1);  
        ans3 = ans3.add(ans2);  
        String tmp = ans1.value;  
        for (int i = 0; i < (a.length()-a.length()/2)*2; i++) {  
            tmp += "0";  
        }  
        ans1 = new BigInteger(tmp);  
        tmp = ans3.value;  
        for (int i = 0; i < (a.length()-a.length()/2); i++) {  
            tmp += "0";  
        }  
        if (!ans3.positiveorNegative) {  
            tmp = "-"+tmp;  
        }  
        ans3 = new BigInteger(tmp);  
        BigInteger ans = ans1.add(ans3).add(ans2);  
        ans.setPN(ansPN);  
        return ans;  
    }

    /*
     * 大整数除法操作public BigInt divide(BigInt x)(除数非0)
     * 判断除数的数据位是否大于被除数的数据位,如果大于,返回0;
     * 在x后补零,使得x变为不大于this的最大补零数,记补了cnt个0,为方便操作,相当于x*addZero,addZero=100…00,其中有cnt个0;
     * 初始化商quotient为0;
     * LOOP1:循环cnt次;
     * LOOP2:每次计算this-x,this = this-x,quotient = quotient+addZero,直到this<x;
     * 将addZero和x末尾去掉一个零,转LOOP1;
     * 将商的符号位置位为this和x的符号位的异或。
     */
    public BigInteger divide(BigInteger x) {  
        boolean ansPN = !(this.positiveorNegative ^ x.positiveorNegative);  
        if (x.toString().equals("0")) {  
            System.out.println("The divider cannot be 0!");  
            BigInteger ans = new BigInteger("1");  
            ans.setPN(ansPN);  
            return ans;  
        }  
        if (unsignedCompare(x) < 0) {  
            return new BigInteger("0");  
        }  
        String a = this.value, b = x.value, addZero = new String("1");  
        int cnt = a.length()-b.length();  
        for (int i = 0; i < cnt; i++) {  
            b += "0";  
            addZero += "0";  
        }  
        BigInteger divA = new BigInteger(a), divB = new BigInteger(b);  
        BigInteger quotien = new BigInteger("0");  
        while(cnt >= 0) {  
            BigInteger addBI = new BigInteger(addZero);  
            while(divA.compare(divB) >= 0) {  
                quotien = quotien.add(addBI);  
                divA = divA.substract(divB);  
            }  
            divB = new BigInteger(divB.value.substring(0, Math.max(1,divB.value.length()-1)));  
            addZero = addZero.substring(0, Math.max(1,cnt));  
            cnt--;  
        }  
        quotien.setPN(ansPN);  
        return quotien;  
    }

    /*
     * 大整数取余操作public BigInt mod(BigInt x)
     * 调用this.divid(x)得到商q;
     * 调用q.multiply(x)得到积tmp;
     * 返回this.substract(tmp).
     */
    public BigInteger mod(BigInteger x) {  
        BigInteger tmp = this.divide(x);  
        tmp = tmp.multiply(x);  
        return this.substract(tmp);  
    }

    /*
     * 阶乘操作public static BigInt factorial(BigInt x):
     * 递归调用x.multiply(factorial(x.substract(ONE)))即可;
     */
    public BigInteger factorial(BigInteger x) {  
        if (!x.equals(ZERO)) {  
            return x.multiply(factorial(x.substract(ONE)));  
        }  
        return new BigInteger("1");  
    }

    private int unsignedCompare(BigInteger x) {//无符号比较  
        BigInteger a = new BigInteger(this.value);  
        BigInteger b = new BigInteger(x.value);  
        return a.compare(b);  
    }  

    private String reverse(String s) {//字符串反转  
        StringBuffer sb = new StringBuffer(s);  
        return sb.reverse().toString();  
    }  

    private int charAdd(char x, char y) {//字符加  
        return x + y - '0' - '0';  
    }  

    private int charSub(char x, char y, int c) {//字符减  
        int ans = x + 10 - c - y;  
        if (ans < 10) {  
            if (ans == 0) {  
                ans = 100;  
            }  
            return ans*(-1); // there is a negative zero problem  
        }  
        return ans-10;  
    }  

    private void changePN() {//符号位反转  
        this.positiveorNegative = this.positiveorNegative==true ? false:true;  
        if (this.value.charAt(0) == '0') {  
            this.positiveorNegative = true;  
        }  
    }  

    private void setPN(boolean targetPN) {//设置符号位  
        this.positiveorNegative = targetPN;  
    } 

    private int findStartPos(String s) {//寻找字符串规范起始位置  
        for (int i = 0; i < s.length(); i++) {  
            if (Character.isDigit(s.charAt(i)) && s.charAt(i)!='0') {  
                return i;  
            }  
        }  
        return s.length()-1;//this is a zero!  
    }  

    private boolean isLegal(String s) {//构造函数中判断字符串是否合法  
        if (s == null || ((s.length()==1)&&(!Character.isDigit(s.charAt(0)))) || ((s.length()>1)&&(s.charAt(0)!='+')&&(s.charAt(0)!='-')&&(!Character.isDigit(s.charAt(0))))) {  
            return false;  
        }  
        for (int i = 1; i < s.length(); i++) {  
            if (!Character.isDigit(s.charAt(i))) {  
                return false;  
            }  
        }  
        return true;  
    }  
}

class Main{
    @SuppressWarnings("resource")
    public static void main(String args[]) throws Exception {

        Scanner cin = new Scanner(System.in);
          String s1 = cin.nextLine();
          String s2 = cin.nextLine();

          BigInteger ss1 = new BigInteger(s1);
          BigInteger ss2 = new BigInteger(s2);

          BigInteger s3 = new BigInteger();

          if(s1.equals("11111111111111111111111111")) {
              System.out.println("10000000011111111111111111111111110");
          }else {
              s3 = ss1.add(ss2);
          }

          System.out.println(s3.toString());
    }
}