首页 星云 工具 资源 星选 资讯 热门工具
:

PDF转图片 完全免费 小红书视频下载 无水印 抖音视频下载 无水印 数字星空

洛谷P1226 【模板】快速幂

编程知识
2024年08月07日 08:39

1.快速幂模板

前置知识

一个数字n,它的二进制位数一定是log2n向下取整+1;

快速幂模板代码

这段代码实现了快速幂算法(Exponentiation by squaring),用来计算 ( an ) 的值,其中 ( a ) 和 ( n ) 都是整数。

int quickpow(int a, int n)
{
    int res = 1;  // 初始化结果为1,因为任何数的0次幂都是1

    while (n) {   // 当指数n不为0时,继续执行循环
        if (n & 1)  // 如果n的最低位为1(即n是奇数)
            res = res * a;  // 将当前底数a乘到结果中
        a = a * a;   // 将底数a平方,相当于底数翻倍,指数减半
        n >>= 1;     // 将指数n右移一位,相当于将指数减半
    }

    return res;  // 返回计算结果
}

现在逐句解析每一行代码的作用:

  1. int res = 1;

    • 初始化变量 res 为1,这是最终结果的初始值。任何数的0次幂都是1。
  2. while (n) {

    • 进入一个循环,条件是当指数 n 不为0时继续执行。循环将持续执行直到 n 变为0。
  3. if (n & 1)

    • 判断当前的指数 n 是否为奇数,使用位运算 n & 1 来判断。如果 n 的最低位(即最右边的二进制位)为1,则说明 n 是奇数。
  4. res = res * a;

    • 如果 n 是奇数,则将当前的底数 a 乘到结果 res 中。这步实现了快速幂算法中的乘法操作。
  5. a = a * a;

    • 然后将底数 a 自乘,即 a 变成 a^2。这一步相当于将底数翻倍,对应于指数减半的操作。
  6. n >>= 1;

    • 将指数 n 右移一位,即 n 变成 n / 2。这一步实现了快速幂算法中的指数减半操作。
  7. 循环回到第2步,直到 n 变为0,退出循环。

  8. return res;

    • 返回最终计算得到的结果 res,即底数 a 的指数 n 次幂的值。

这段代码利用了快速幂算法的思想,通过迭代和位运算的方式,将指数的计算复杂度从 ( O(n) ) 优化到 ( O(log n) ),显著提高了计算效率。

快速幂算法的形象解释

快速幂算法的例题

【模板】快速幂

题目描述

给你三个整数 \(a,b,p\),求 \(a^b \bmod p\)

输入格式

输入只有一行三个整数,分别代表 \(a,b,p\)

输出格式

输出一行一个字符串 a^b mod p=s,其中 \(a,b,p\) 分别为题目给定的值, \(s\) 为运算结果。

样例 #1

样例输入 #1

2 10 9

样例输出 #1

2^10 mod 9=7

提示

样例解释

\(2^{10} = 1024\)\(1024 \bmod 9 = 7\)

数据规模与约定

对于 \(100\%\) 的数据,保证 \(0\le a,b < 2^{31}\)\(a+b>0\)\(2 \leq p \lt 2^{31}\)

答案

这题直接套用快速幂算法的模板,只需要每一步我们加上取模运算即可,注意数据需要开long long类型

#include<iostream>
using namespace std;
long long  quickpow(long long  a, long long  n,long long p)
{
	long long res = 1;
	while (n) {
		if (n & 1) res = (res * a)%p;
		a = (a * a)%p;
		n >>= 1;
	}
	return res;
}
int main()
{
	long long  a, b, p;
	cin >> a >> b >> p;
	printf("%lld^%lld mod %lld=%lld", a, b, p, quickpow(a, b, p));
	return 0;
}
From:https://www.cnblogs.com/Tomorrowland/p/18346407
本文地址: http://www.shuzixingkong.net/article/869
0评论
提交 加载更多评论
其他文章 后端开发学习敏捷需求-->专题的目标与价值成效
专题的目标与价值成效 什么是专题 公司或企业为了抓住业务机会或者解决痛点问题,而采取的具体的行动和举措 专题的目标分析 1.业务调研了解目标的预期 利用5W2H来进行专题分析 what——是什么?目的是什么?作什么工作? 专题是什么 专题产生的背景是什么 专题的目标是什么,要达到怎样的预期,包含那些
后端开发学习敏捷需求-->专题的目标与价值成效
《最新出炉》系列初窥篇-Python+Playwright自动化测试-65 - Canvas元素推拽-番外篇
1.简介 上一篇宏哥想了好多办法都没有演示成功的拖拽Canvas元素,宏哥也说的太绝对了,给大家造成困惑或者误导。一连好几天吃饭睡觉都不怎么香了,脑子中始终对这件事耿耿于怀,自己问自己难道就真的没有办法了吗?突然想到了一种办法抱着试一下的心态,结果出乎意料但是又在情理之中:成功推拽了!!!此刻地心情
《最新出炉》系列初窥篇-Python+Playwright自动化测试-65 - Canvas元素推拽-番外篇 《最新出炉》系列初窥篇-Python+Playwright自动化测试-65 - Canvas元素推拽-番外篇 《最新出炉》系列初窥篇-Python+Playwright自动化测试-65 - Canvas元素推拽-番外篇
Cython将Numpy数组转为自定义结构体
这篇文章介绍了在Cython中定义结构体,并在Python的Numpy数组/MemoryView和自定义结构体之间进行数据转换的方法。Cython有着非常Pythonic的编程范式,又具有接近于C语言的性能,对于Python开发者而言确实是一个很棒的工具。
结合实例看 maven 传递依赖与优先级,难顶也得上丫
开心一刻 想买摩托车了,但是钱不够,想找老爸借点 我:老爸,我想买一辆摩托车,上下班也方便 老爸:你表哥上个月骑摩托车摔走了,你不知道?还要买摩托车? 我:对不起,我不买了 老板:就是啊,骑你表哥那辆得了呗,买啥新的 先抛问题 关于 maven 的依赖(dependency),我相信大家多少都知道点
结合实例看 maven 传递依赖与优先级,难顶也得上丫 结合实例看 maven 传递依赖与优先级,难顶也得上丫 结合实例看 maven 传递依赖与优先级,难顶也得上丫
神经网络之卷积篇:详解边缘检测示例(Edge detection example)
详解边缘检测示例 卷积运算是卷积神经网络最基本的组成部分,使用边缘检测作为入门样例。在这个博客中,会看到卷积是如何进行运算的。 在之前的博客中,说过神经网络的前几层是如何检测边缘的,然后,后面的层有可能检测到物体的部分区域,更靠后的一些层可能检测到完整的物体,这个例子中就是人脸。在这个博客中,会看到
神经网络之卷积篇:详解边缘检测示例(Edge detection example) 神经网络之卷积篇:详解边缘检测示例(Edge detection example) 神经网络之卷积篇:详解边缘检测示例(Edge detection example)
强化学习性能测试方法:取最后10个epoch的testing epoch的均值 —— 强化学习中的一种性能测试方法
参考: https://www.cnblogs.com/devilmaycry812839668/p/17813337.html The Actor-Mimic and expert DQN training curves for 100 training epochs for each of th
Canvas简历编辑器-图形绘制与状态管理(轻量级DOM)
Canvas简历编辑器-图形绘制与状态管理(轻量级DOM) 在前边我们聊了数据结构的设计和剪贴板的数据操作,那么这些操作都还是比较倾向于数据相关的操作,那么我们现在就来聊聊基本的图形绘制以及图形状态管理。 在线编辑: https://windrunnermax.github.io/CanvasEdi
Canvas简历编辑器-图形绘制与状态管理(轻量级DOM) Canvas简历编辑器-图形绘制与状态管理(轻量级DOM)
.NET 免费开源工业物联网网关
IoTClient 是一个针对物联网 (IoT) 领域的开源客户端库,它主要用于实现与各种工业设备之间的通信。这个库是用 C# 编写的,并且基于 .NET Standard 2.0,这意味着可以用于多个版本的.NET,包括 .NET Framework、.NET Core、.NET 5 及以上版本,
.NET 免费开源工业物联网网关 .NET 免费开源工业物联网网关 .NET 免费开源工业物联网网关