大整数相乘（分治）

参考了（感谢）：http://blog.csdn.net/jeffleo/article/details/53446095

继续变换：XY=AC2^n+[(A-B)(D-C)+AC+BD]2^n/2+BD

把原来的AC、AD、BC、BD四个乘法转化成了AC、（A-B）（D-C）、BD三个乘法

时间复杂度从O(n^2)变成O(n^1.59 )

import java.util.Scanner;

import static java.lang.Math.pow;

public class Main {
    public static int flag(int x) {
        x = (x > 0)? 1:-1;
        return x;
    }
    public static int multiply(int x, int y, int n) {
        int flag = flag(x)*flag(y);
        x = Math.abs(x);
        y = Math.abs(y);
        if (x == 0 || y == 0) {
            return 0;
        } else if (n == 1) {
            return flag * x * y;
        } else {
            //分割计算
            int A = x / (int) pow(10, n/2);
            int B = (int) (x - A*(pow(10, n / 2)));
            int C = (int) (y / pow(10, n / 2));
            int D = (int) (y - C*(pow(10, n / 2)));
            //分治计算
            int AC = multiply(A, C, n / 2);
            int BD = multiply(B, D, n / 2);
            int ABDC = multiply((A - B), (D - C), n / 2) + AC + BD;
            return (int) (flag*(AC*pow(10, n) + ABDC * pow(10, (n/2)) + BD));
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();
        int n = sc.nextInt();
        System.out.println(multiply(x,y,n));
        System.out.println(x*y);
        sc.close();
    }
}