大整数相乘(分治)

简介: 参考了(感谢):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();
    }
}
目录
相关文章
|
Linux C++ Windows
c++ 通过域名获取ip(跨平台)
c++ 通过域名获取ip(跨平台)
1571 0
|
存储 JSON 数据建模
鸿蒙 HarmonyOS NEXT端云一体化开发-云数据库篇
云数据库采用存储区、对象类型、对象三级结构,支持灵活的数据建模与权限管理,可通过AGC平台或本地项目初始化,实现数据的增删改查及端侧高效调用。
786 1
|
10月前
|
SQL 运维 安全
CI/CD 中的安全闸门:不是“卡人”的流程,而是帮你少背锅的自动化安全测试流水线
CI/CD 中的安全闸门:不是“卡人”的流程,而是帮你少背锅的自动化安全测试流水线
431 4
|
11月前
|
存储 开发者 Python
Python语言程序基本结构详解(零基础也能看懂的Python程序结构入门指南)
教程来源:https://www.vpshk.cn/教程Python程序结构清晰,包含导入模块、变量定义、函数封装和主逻辑四部分。从“Hello, World!”入门,掌握基本结构是学习Python的关键,有助于编写易读、可维护的代码,为进阶打下坚实基础。
|
10月前
|
机器学习/深度学习 监控 数据可视化
基于YOLOv8的蚊蝇位置智能检测识别项目|完整源码数据集+PyQt5界面+完整训练流程+开箱即用!
基于YOLOv8的蚊蝇智能检测项目,集成PyQt5可视化界面,支持图片、视频、摄像头实时检测,提供完整源码、数据集、预训练模型及训练教程,开箱即用,助力公共卫生、农业环境等场景下的害虫智能监测与管理。
437 3
|
10月前
|
弹性计算 负载均衡 测试技术
阿里云CDT云数据传输是什么?免费220GB流量如何领取?CDT详细介绍及问题解答FAQ
阿里云CDT是网络带宽统一计费平台,自动聚合ECS、EIP、SLB等产品流量,享每月220GB免费额度,用量越大单价越低,支持按量付费、成本分摊,降本增效更可控。
|
10月前
|
SQL 人工智能 监控
超越单点AI:智能体来了(西南总部)解构 Multi-Agent 系统的协同设计哲学
智能体来了(西南总部)提出,AI 下半场的核心是“组织力”竞争。本文深度解析 Multi-Agent 系统如何通过角色分工、动态通信、共享记忆与自省机制,构建协同“数字兵团”,实现企业生产力的范式跃迁,推动运营工程师从提示词写作者迈向系统架构师。
409 2
|
10月前
|
存储 JSON 自然语言处理
十一年实战沉淀:淘宝商品评论数据深度解析与落地技巧
深耕淘宝评论分析11年,亲历数据结构迭代与解析挑战。本文详解评论数据核心字段、解析难点及破局技巧,分享实战验证的标准化流程,涵盖字符处理、动态规则、高效存储等关键环节,助力精准情感分析与用户洞察。
1038 1
|
11月前
|
数据采集 监控 数据管理
如何评估数据质量?数据质量管理该如何进行?
本文探讨企业数据质量管理的核心挑战与解决方案,通过真实案例揭示数据不一致、重复、延迟等问题对业务决策的严重影响。提出从完整性、准确性、一致性等六大维度评估数据质量,并构建“定义-测量-分析-改进”的闭环管理体系。强调以关键数据资产为起点,推动业务与技术协同,实现数据质量的可持续管控,最终建立组织内对数据的信任与共识。
|
10月前
|
人工智能 缓存 调度
深度解析:AI Agent 指挥官如何通过调度策略降低算力成本
2026年,算力成本成AI落地最大瓶颈。本文提出“AI Agent指挥官”范式,聚焦成本感知调度:通过异构模型路由、语义缓存增强、异步并行批处理与动态提示精简四大策略,实现智能与经济的最优平衡,实测降本达83%。(239字)
825 0