首页 > 其他分享 >洛谷P1226 【模板】快速幂

洛谷P1226 【模板】快速幂

时间:2024-08-07 09:40:44浏览次数:15  
标签:洛谷 int res 底数 long P1226 快速 模板

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;
}

标签:洛谷,int,res,底数,long,P1226,快速,模板
From: https://www.cnblogs.com/Tomorrowland/p/18346407

相关文章

  • 洛谷P1208 [USACO1.3] 混合牛奶 Mixing Milk
    P1208[USACO1.3]混合牛奶MixingMilk题目描述由于乳制品产业利润很低,所以降低原材料(牛奶)价格就变得十分重要。帮助Marry乳业找到最优的牛奶采购方案。Marry乳业从一些奶农手中采购牛奶,并且每一位奶农为乳制品加工企业提供的价格可能相同。此外,就像每头奶牛每天只能挤出固......
  • 洛谷 P4910题解
    题目大意现在穿T次手串,每根手串的长度分别为不同的n,有木和金两种珠子,相邻两颗珠子必须有一个是金。题目思路分析我们现在设穿到第n个珠子时用金的方案数为f[1][n],用木的方案数为f[0][n]如果第n个珠子为金,那么前一颗珠子是什么都可以,因此f[1][n]=f[1][n-1]+f[0][n-1]而如果......
  • 洛谷P5250 【深基17.例5】木材仓库
    【深基17.例5】木材仓库题目描述博艾市有一个木材仓库,里面可以存储各种长度的木材,但是保证没有两个木材的长度是相同的。作为仓库负责人,你有时候会进货,有时候会出货,因此需要维护这个库存。有不超过100000条的操作:进货,格式1Length:在仓库中放入一根长度为Length(不超过\(10......
  • 【CDQ分治】【模板】三维偏序(陌上花开)
    P3810【模板】三维偏序(陌上花开)-洛谷|计算机科学教育新生态(luogu.com.cn)#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;template<typenameT>structBIT{#ifndeflowbit#definelowbit(x)(x&(-x));#endifintn;vector<T&......
  • 织梦dedecms怎么更换模板
    更换Dedecms模板是一个相对简单的过程,本指南将详细介绍如何操作。步骤下载模板从Dedecms官方网站或其他可信来源下载所需的模板。上传模板解压缩下载的模板文件,并将所有文件上传到Dedecms安装目录中的"templets"文件夹。管理模板登录Dedecms后台,进入......
  • 洛谷P1209修理牛棚 Barn Repair
    [USACO1.3]修理牛棚BarnRepair题目描述在一个月黑风高的暴风雨夜,FarmerJohn的牛棚的屋顶、门被吹飞了好在许多牛正在度假,所以牛棚没有住满。牛棚一个紧挨着另一个被排成一行,牛就住在里面过夜。有些牛棚里有牛,有些没有。所有的牛棚有相同的宽度。宽度为1自门遗失以后......
  • 洛谷P1081【NOIP2012提高组】开车旅行
    题目见[NOIP2012提高组]开车旅行-洛谷(懒得打题目了)我们直接上代码#include<iostream>#include<cstdlib>#include<cstdio>#include<cmath>#include<cstring>#include<iomanip>#include<algorithm>#include<ctime>#include<queue>......
  • CPP 基于模板的类型相同判断[CPP template-8]
    今天的代码是今年早些时候写的,std库中也有类似的方法。这里我们把思路理一下,写一个自己的类型相同判断模板♪(´▽`)在python中//Typecomparison//基本操作写于24/5/2//功能是通过模板元编程进行两个变量类型的对比//(没错,python中易如反掌的事情,在CPP中需要不一般......
  • C++(模板)
    目录1.函数模板(FunctionTemplates)1.1基本语法:1.2使用示例:2.类模板(ClassTemplates)2.1基本语法:2.2使用示例:3.模板的特性在C++中,模板是泛型编程的重要工具,用于编写通用和可重用的代码。模板主要有两种类型:函数模板和类模板。1.函数模板(FunctionTemplates)函数模板允......
  • 洛谷题单指南-前缀和差分与离散化-P1904 天际线
    原题链接:https://www.luogu.com.cn/problem/P1904题意解读:给出(左端点,高度,右端点)表示的若干建筑,要输出其轮廓,所谓轮廓就是每个点被覆盖的最高建筑的高度所描绘的线。解题思路:如果能计算每个点被覆盖的最高建筑的高度,用数组h[10005]保存,那么输出轮廓的过程只需要枚举每一个点,如......