大整数相乘(分治)

简介: 参考了(感谢):http://blog.csdn.net/jeffleo/article/details/53446095继续变换:XY=AC2^n+[(A-B)(D-C)+AC+BD]2^n/2+BD把原来的A...

参考了(感谢):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();
    }
}
目录
相关文章
|
5天前
|
算法
【算法】前缀和——除自身以外数组的乘积
【算法】前缀和——除自身以外数组的乘积
|
1月前
|
算法
【算法】二分查找(整数二分和浮点数二分)
算法学习——二分查找(整数二分和浮点数二分)
25 0
【算法】二分查找(整数二分和浮点数二分)
|
2月前
|
机器学习/深度学习 存储 人工智能
每日练习之矩阵乘法——斐波那契公约数
每日练习之矩阵乘法——斐波那契公约数
21 0
|
3月前
|
人工智能
游游的选数乘积
游游的选数乘积
38 3
|
3月前
|
算法 测试技术 C#
【数学】【数论】【最大公约数】1819. 序列中不同最大公约数的数目
【数学】【数论】【最大公约数】1819. 序列中不同最大公约数的数目
|
3月前
|
算法 测试技术 C++
【组合数学】【动态规划】【前缀和】1735生成乘积数组的方案数
【组合数学】【动态规划】【前缀和】1735生成乘积数组的方案数
|
9月前
|
存储
A除于B(大数相除)
A除于B(大数相除)
53 0
|
10月前
|
算法
【学会动态规划】乘积为正数的最长子数组长度(21)
【学会动态规划】乘积为正数的最长子数组长度(21)
47 0
|
机器学习/深度学习 算法
【贪心算法】最大整数
【贪心算法】最大整数
77 0
|
C++
C++ 超大整数相加、相乘的精确求解,以及10000的阶乘
C++ 超大整数相加、相乘的精确求解,以及10000的阶乘
98 0