[PKU2389]Bull Math (大数运算)

Description

Bulls are so much better at math than the cows. They can multiply huge integers together and get perfectly precise answers ... or so they say. Farmer John wonders if their answers are correct. Help him check the bulls' answers. Read in two positive integers (no more than 40 digits each) and compute their product. Output it as a normal number (with no extra leading zeros).

FJ asks that you do this yourself; don't use a special library function for the multiplication.

Input

* Lines 1..2: Each line contains a single decimal number.

Output

* Line 1: The exact product of the two input lines

Sample Input

11111111111111
1111111111

Sample Output

12345679011110987654321

Source

USACO 2004 November

已经最近一直在工作了。很少机会刷题了，所以趁今天有水了一道题。

就是最简单的大数乘法(此题数据不强，没有多余0开头的数字和没有negative integer~~).

看到大数运算，第一想法是果断用Java神功护体，BigDecimal!!!

但是这样没什么意思呀。。所以想了想就自己写了，水题嘛也不要太水过了~

其实大数运算的核心思想都是用数组来储存每一个位置上的数，这样只要数组足够大，理论上可以计算无穷大的运算。因为每个数字上（譬如int）都不超过10，所以储存下来卓卓有余。

然后就模拟我们小学的加减乘除运算。就得出答案了~

题目传送门:http://poj.org/problem?id=2389

Java Code Here:

import java.util.Scanner;

public class Main {

    public static void main(String[] args){
        Scanner sc = new Scanner( System.in );
        BigMultiplicative bm = new BigMultiplicative( 500 );
        while(sc.hasNext()){
            String a = sc.next();
            String b = sc.next();
            System.out.println( bm.doMultiplicative( a.toCharArray(), b.toCharArray() ) );

        }
    }
}

class BigMultiplicative {

    private int[] answer;

    private int capacity;

    private int length = 0;

    public int getCapacity() {
        return capacity;
    }

    public void setCapacity( int capacity ) {
        this.capacity = capacity;
    }

    public int getLength() {
        return length;
    }

    public void setLength( int length ) {
        this.length = length;
    }

    public BigMultiplicative( int capacity ) {
        this.capacity = capacity;
    }

    public String doMultiplicative(char[] a,char[] b){
        answer = new int[capacity];
        String as = String.valueOf( a );
        String bs = String.valueOf( b );
        for(int i=as.length()-1;i>=0;i--){
            for(int j=bs.length()-1;j>=0;j--){
                int index = bs.length() - j -1 + (as.length()-1-i);
                int temp = Integer.parseInt(String.valueOf(as.charAt( i ))) * Integer.parseInt(String.valueOf(bs.charAt( j )));
                int over = temp / 10;
                answer[index]  += temp%10;
                if(answer[index] >= 10){
                    int carry = answer[index];
                    answer[index] = ( char )( answer[index] % 10 );
                    answer[index+1]+=carry/ 10;
                }
                if(over!=0){
                    answer[index +1 ] += over;
                    if(index +1 > length){
                        length = index+1;
                    }
                }
                if(index > length){
                    length = index;
                }
            }
        }
        if(answer[length+1] != 0){
            length++;
        }
        StringBuilder sb = new StringBuilder();
        for(int i=length;i>=0;i--){
            sb.append( (int)answer[i] );
        }
        for(int i=0;i<sb.length();i++){
            if(sb.charAt( i) == '0'){
                sb.deleteCharAt( 0 );
                i--;
            }else{
                break;
            }
        }
        return sb.toString();
    }

}