【leetcode 力扣刷题】数学题之计算次幂//次方:快速幂

利用乘法求解次幂问题—快速幂

  • 50. Pow(x, n)
  • 372. 超级次方

50. Pow(x, n)

题目链接:50. Pow(x, n)
题目内容:
在这里插入图片描述
题目就是要求我们去实现计算x的n次方的功能函数,类似c++的power()函数。但是我们不能使用power()函数直接得到答案,那样这道题就失去了考察的意义。
前面提到乘法a*b可以看作是b个a相加,用加法来完成乘法;x的n次方,就是n个x相乘,那么同样可以用乘法来代替次幂计算,我们称之为快速幂。比如5^7,就是7个5相乘,快速幂的过程如下:
在这里插入图片描述
第一轮是乘以5,第二轮乘以5*5,第三轮乘以(5*5)*(5*5),也就是每一轮乘的数都在加倍,这样就能够在log^n的时间复杂度内完成x^n的计算。代码实现如下(C++):


class Solution {
public:double myPow(double x, int n) {//先处理特殊情况if(x == 0) return 0.0;if(x == 1) return 1.0;if(n == 0) return 1.0;bool flage = false;long _n = n;//如果n是负数,x^n = 1/(x^|n|)if(_n < 0){flage = true;_n = -_n;}double ans = 1;double mul = x;//快速幂主体过程while(_n){  if(_n&1)  //如果n末位为1,就乘以mulans *= mul;      mul *= mul; //mul翻倍_n >>= 1; //n右移一位}return flage ? 1.0/ans : ans; //判断是否需要变成倒数}
};

372. 超级次方

题目链接:372. 超级次方
题目内容:
在这里插入图片描述
看起来和上一题是差不多的,但是由于b是一个非常大的正整数,以数组形式给出[1,0,3,4]就表示1034【末位是个位,然后是十位,然后是百位,最前面的是最高位】。其中1 <= b.length <= 2000说明b可以达到10^1999的程度,根本没法用double、long long等数据类型来存储这么大的数,所以在运算过程中也不能直接把b转换成一个数或者每一位转换成一个数,需要其他方法:
在这里插入图片描述
将每一位b[i]的数值b[i]*10^(m-1-i)【其中m是b.length】分解成b[i]和10^(m-1-i)两部分,每次先求a^(10^(m-1-i))得到A,再求A^b[i]。a^(10^(m-1-i))随着i的减小越来越大,但是可以看作是上一轮的A^10。
由于每次次幂结果都要mod 1337,所以结果是不会溢出的,a^(10^(m-1-i))每一次用上一轮的A^10来表示就解决了b很大的问题。另外需要注意的是(a*b) mod k =( (a mod k) * (b mod k) ) mod k。
a^(10^(m-1-i))和A^b[i]以及A^10都用快速幂求解。快速幂过程中根据(a*b) mod k =( (a mod k) * (b mod k) ) mod k加上求模操作。代码如下(C++):

class Solution {
public://快速幂long quick_pow(int a, int n){int ans = 1;int mul = a;while(n){if(n&1)//加上求模操作ans = ( (ans % 1337) * (mul % 1337)) % 1337;//mul也加上求模操作mul = ((mul % 1337) * (mul % 1337)) % 1337;n>>=1;}return ans;}int superPow(int a, vector<int>& b) {int ans = 1;        for(int j = b.size() - 1; j >= 0; j--){ans =( (ans % 1337) * (quick_pow(a,b[j]) % 1337) ) % 1337;//每次a都在上一次的基础上,变成其10次方a = quick_pow(a, 10);}return ans;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/117118.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

ARM Cortex-M 的 SP

文章目录 1、栈2、栈操作3、Cortex-M中的栈4、MDK中的SP操作流程5、Micro-Lib的SP差别1. 使用 Micro-Lib2. 未使用 Micro-Lib 在嵌入式开发中&#xff0c;堆栈是一个很基础&#xff0c;同时也是非常重要的名词&#xff0c;堆栈可分为堆 (Heap) 和栈 (Stack) 。 栈(Stack): 一种…

EG1164大功率同步整流升压模块开源,最高效率97%

EG1164大功率同步整流Boost升压电源模块&#xff0c;最高效率97%&#xff0c;输入电压8~50V&#xff0c;输出电压8~60V可调&#xff0c;最大功率300瓦以上&#xff0c;开关频率219kHz。 白嫖了张嘉立创的彩色丝印券就随便画了个板试试&#xff0c;第一次打彩色丝印。 因为我测…

flutter plugins插件【一】【FlutterJsonBeanFactory】

1、FlutterJsonBeanFactory 在Setting->Tools->FlutterJsonBeanFactory里边自定义实体类的后缀&#xff0c;默认是entity 复制json到粘贴板&#xff0c;右键自己要存放实体的目录&#xff0c;可以看到JsonToDartBeanAction Class Name是实体名字&#xff0c;会默认加上…

基于硬件隔离增强risc-v调试安全1_问题描述

安全之安全(security)博客目录导读 2023 RISC-V中国峰会 安全相关议题汇总 说明&#xff1a;本文参考RISC-V 2023中国峰会如下议题&#xff0c;版权归原作者所有。

每日一题 2511. 最多可以摧毁的敌人城堡数目

难度&#xff1a;简单 翻译&#xff1a;寻找距离最远的 1 和 -1 的组合&#xff0c;要求它们之间只有0 class Solution:def captureForts(self, forts: List[int]) -> int:res, t 0, -1for i, fort in enumerate(forts):if fort -1 or fort 1:if t > 0 and fort ! f…

前端Vue自定义得分构成水平柱形图组件 可用于系统专业门类得分评估分析

引入Vue自定义得分构成水平柱形图组件&#xff1a;cc-horBarChart 随着技术的发展&#xff0c;传统的开发方式使得系统的复杂度越来越高&#xff0c;一个小小的改动或小功能的增加可能会导致整体逻辑的修改&#xff0c;造成牵一发而动全身的情况。为了解决这个问题&#xff0c…

扫盲:常用NoSQL数据库

前言 关系型数据库产品很多&#xff0c;如 MySQL、Oracle、Microsoft SQL Sever 等&#xff0c;但它们的基本模型都是关系型数据模型。 非关系型数据库又称为&#xff1a;NoSQL &#xff0c;没有统一的模型&#xff0c;而且是非关系型的。 常见的 NoSQL 数据库包括键值数据库、…

【前端】Vue2 脚手架模块化开发 -快速入门

&#x1f384;欢迎来到边境矢梦的csdn博文&#x1f384; &#x1f384;本文主要梳理Vue2 脚手架模块化开发 &#x1f384; &#x1f308;我是边境矢梦&#xff0c;一个正在为秋招和算法竞赛做准备的学生&#x1f308; &#x1f386;喜欢的朋友可以关注一下&#x1faf0;&#x…

【MATLAB第70期】基于MATLAB的LightGbm(LGBM)梯度增强决策树多输入单输出回归预测及多分类预测模型(全网首发)

【MATLAB第70期】基于MATLAB的LightGbm(LGBM)梯度增强决策树多输入单输出回归预测及多分类预测模型&#xff08;全网首发&#xff09; 一、学习资料 (LGBM)是一种基于梯度增强决策树(GBDT)算法。 本次研究三个内容&#xff0c;分别是回归预测&#xff0c;二分类预测和多分类预…

系列五、Java操作RocketMQ简单消息之同步消息

一、概述 同步消息的特征是消息发出后会有一个返回值&#xff0c;即RocketMQ服务器收到消息后的一个确认&#xff0c;这种方式非常安全&#xff0c;但是性能上却没有那么高&#xff0c;而且在集群模式下&#xff0c;也是要等到所有的从机都复制了消息以后才会返回&#xff0c;适…

Linux系统Ubuntu以非root用户身份操作Docker的方法

本文介绍在Linux操作系统Ubuntu版本中&#xff0c;通过配置&#xff0c;实现以非root用户身份&#xff0c;进行Docker各项操作的具体方法。 在文章Linux系统Ubuntu配置Docker详细流程&#xff08;https://blog.csdn.net/zhebushibiaoshifu/article/details/132612560&#xff0…

如何使用Puppeteer进行新闻网站数据抓取和聚合

导语 Puppeteer是一个基于Node.js的库&#xff0c;它提供了一个高级的API来控制Chrome或Chromium浏览器。通过Puppeteer&#xff0c;我们可以实现各种自动化任务&#xff0c;如网页截图、PDF生成、表单填写、网络监控等。本文将介绍如何使用Puppeteer进行新闻网站数据抓取和聚…

mac idea启动没反应 无法启动

遇到的问题如下&#xff1a; 启动idea&#xff0c;没反应 无法启动&#xff0c;不论破解还是别的原因&#xff0c;总之无法启动了 应用程序–找到idea–右击显示包内容–Contents–MacOS–打开idea 弹出框提示如下&#xff1a; 双击这个idea可执行文件 1&#xff09;先查看日志…

JS中的new操作符

文章目录 JS中的new操作符一、什么是new&#xff1f;二、new经历了什么过程&#xff1f;三、new的过程分析四、总结 JS中的new操作符 参考&#xff1a;https://www.cnblogs.com/buildnewhomeland/p/12797537.html 一、什么是new&#xff1f; 在JS中&#xff0c;new的作用是通过…

【OpenCV入门】第七部分——图像的几何变换

文章结构 缩放dsize参数实现缩放fx参数和fy参数实现缩放 翻转仿射变换平移旋转倾斜 透视cmath模块 缩放 通过resize()方法可以随意更改图像的大小比例&#xff1a; dst cv2.resize(src, dsize, fx, fy, interpolation)src&#xff1a; 原始图像dsize&#xff1a; 输出图像的…

链表OJ练习(2)

一、分割链表 题目介绍&#xff1a; 思路&#xff1a;创建两个链表&#xff0c;ghead尾插大于x的节点&#xff0c;lhead尾插小于x的节点。先遍历链表。最后将ghead尾插到lhead后面&#xff0c;将大小链表链接。 我们需要在创建两个链表指针&#xff0c;指向两个链表的头节点&…

深入了解Docker镜像操作

Docker是一种流行的容器化平台&#xff0c;它允许开发者将应用程序及其依赖项打包成容器&#xff0c;以便在不同环境中轻松部署和运行。在Docker中&#xff0c;镜像是构建容器的基础&#xff0c;有些家人们可能在服务器上对docker镜像的操作命令不是很熟悉&#xff0c;本文将深…

Android安卓实战项目(13)---记账APP详细记录每天的收入和支出并且分类统计【生活助手类APP】强烈推荐自己也在用!!!(源码在文末)

Android安卓实战项目&#xff08;13&#xff09;—记账APP详细记录每天的收入和支出并且分类统计【生活助手类APP】强烈推荐自己也在用&#xff01;&#xff01;&#xff01;&#xff08;源码在文末&#x1f415;&#x1f415;&#x1f415;&#xff09; 一.项目运行介绍 B站…

如何确认linux的包管理器是yum还是apt,确认之后安装其他程序的时候就需要注意安装命令

打开终端 输入apt&#xff0c;下图中提示未找到命令&#xff0c;则基本上包管理工具就是用yum的 输入yum&#xff0c;我们看到有打印信息&#xff0c;则说明包管理工具是yum的&#xff0c;离线安装命令使用rpm

MongoDB - 安装

一、Docker安装MongoDB 1. 安装 安装版本: 7.0.0 docker run -itd --name mongodb -v C:\\data\\mongodb\\data:/data/db -p 27017:27017 mongo:7.0.0 --auth-v: 将容器目录/data/db映射到本地C:\\data\\mongodb\\data目录&#xff0c;防止容器删除数据丢失-p: 端口映射--aut…