大整数相乘（分治）

╰半橙微兮° 2022-06-07 10:53 144阅读 0赞

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

![这里写图片描述][SouthEast]

继续变换：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();
        }
    }

[http_blog.csdn.net_jeffleo_article_details_53446095]: http://blog.csdn.net/jeffleo/article/details/53446095
[SouthEast]: /images/20220607/dbd146f323ed4279b3c499fe97492d5b.png