快速幂（洛谷题：B2075幂的末尾）

LLintelligence

已于 2024-03-03 09:59:56 修改

阅读量452

点赞数 3

分类专栏：考研计试刷题文章标签：算法

于 2024-02-25 11:10:46 首次发布

本文链接：https://blog.csdn.net/PCLintelligence/article/details/136271788

版权

考研计试刷题专栏收录该内容

15 篇文章 ¥19.90 ¥99.00

订阅专栏

超级会员免费看

本文介绍了快速幂算法，一种用于高效计算幂的递归方法，其时间复杂度由O(n)降低至O(logn)，并通过C语言代码展示了如何使用该算法求解给定数字的末三位幂。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

1、快速幂算法

快速幂算法可以简化幂的求值速度，将原本的暴力求法的时间复杂度O(n)降低为O(logn)，大大降低了代码的运行速度。

快速幂大概是这样的一个递归函数：（求a^b）

题目描述

幂 a^b 的末 3 位数是多少？

输入格式

两个正整数 a，b。1≤1001≤a≤100，1≤100001≤b≤10000。

输出格式

从高位到低位输出幂的末三位数字，中间无分隔符。若幂本身不足三位，在前面补零。

输入输出样例

输入 #1复制

2 3

输出 #1复制

输入 #2复制

7 2011

输出 #2复制

#include <stdio.h>

long long qp (long long a,long long b){//快速幂

了解本专栏

订阅专栏解锁全文

超级会员免费看

确定要放弃本次机会？

福利倒计时

: :

立减 ¥

普通VIP年卡可用

立即使用

LLintelligence

关注关注

3
点赞
踩
3

收藏

觉得还不错? 一键收藏
0
评论
分享

复制链接

分享到 QQ

分享到新浪微博

扫一扫
举报

举报

专栏目录

订阅专栏

夜深人静写算法（三十）- 二分快速幂

英雄哪里出来

02-08

6788

开启数论的征程

洛谷【算法1-1】模拟与高精度 python版

m0_73354184的博客

02-19

534

洛谷题单，蓝桥备赛

参与评论您还未登录，请先登录后发表或查看评论

洛谷 P1965 转圈游戏 —— 快速幂

aodan5477的博客

09-14

143

题目：https://www.luogu.org/problemnew/show/P1965 居然真的就只是 ( x + m * 10k % n ) % n 代码如下： #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> usi...

B2075 幂的末尾(洛谷)

yangrenrui的博客

02-08

502

从高位到低位输出幂的末三位数字，中间无分隔符。若幂本身不足三位，在前面补零。两个正整数 a，b。a的b次方的末 3 位数是多少？

洛谷之快速幂

xoxcu的博客

02-23

385

这道题也是看了题解才明白的。感谢大神指点。对幂的奇偶进行判断假设我们拿到了 x=3x = 3x=3，并且 p=11p = 11p=11。想求 3113^{11}311。·第一层循环。b=11b = 11b=11，一个奇数。将 3113^{11}311 分解为 31∗(32)53^1 * (32)531∗(32)5 来看。本层只需把 ans∗=31ans *= 3^1ans∗=31。那后面的呢？...

洛谷B2075 幂的末尾

旺旺的碎冰冰~的博客

03-15

292

洛谷B2075 幂的末尾

洛谷 | P1226 【快速幂】

Wonz

03-20

605

快速幂 题目链接题目描述输入b，p，k的值，求b^p mod k的值。其中b，p，k*k为长整型数。输入输出格式时空限制时间：1000ms 空间：128MB 代码 #include <iostream> #include <cstdio> using namespace std; typedef long long LL; //求 a^b % m，迭...

B2075 幂的末尾.c

01-22

在编写C语言程序解决洛谷网的B2075 幂的末尾问题时，首先要理解题目的要求。题目的大致内容是：给定两个整数a和b，要求编写一个程序计算a的b次幂的末尾数字是多少。例如，2的5次幂是32，末尾数字为2。在C语言中，...

洛谷p1735 字母迷宫

最新发布

04-23

嗯，用户需要解决洛谷P1735字母迷宫的问题，我得仔细看看题目要求。首先题目是字母迷宫，应该涉及到路径搜索或者动态规划之类的算法。可能题目里要求从起点到终点，收集特定字母或者满足某种条件。首先，我得回忆...

洛谷-矩阵快速幂-(矩阵加速整理)

m0_52398496的博客

09-13

406

给你一个数列a，1

算法-欧拉定理（洛谷-P5091）(十进制快速幂实现)（包含源程序）.rar

09-16

算法-欧拉定理（洛谷-P5091）(十进制快速幂实现)（包含源程序）.rar

洛谷 P3390 矩阵快速幂

chenzaiyu的博客

01-13

430

题目概述给定n*n的矩阵A，求A^k n<=100, k 输出时对每个元素对10^9+7取模解题思路设一n*n的矩阵为A，其元素为A[i,j](1 则A*A可用以下代码实现： for i:=1 to n do for j:=1 to n do for k:=1 to

[二分] 洛谷P1226 快速幂

OI - IceCab

08-06

258

题目输入b，p，k的值，求b^p mod k的值。其中b，p，k*k为长整型数。做法 快速幂讲解代码代码1：没有位运算 #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #def...

洛谷 P1659【manacher】【快速幂】

willem248的博客

09-09

159

【代码】洛谷 P1659【manacher】【快速幂】

洛谷P1226 快速幂

ThisIsHelen的博客

07-22

324

Hi guys~ 今天我又不知道写什么题了… 所以疯狂翻题单… 啊哈就这个吧… // // main.cpp // 快速幂 // // Created by Helen on 2020/4/6. // Copyright © 2020 Helen. All rights reserved. // #include <iostream> using namespace std; long long f(long long b,long long p,long long k) {

洛谷P1226 快速幂

陈颜的博客

02-03

5728

洛谷P1226 快速幂 传送门这道题最暴力的写法是while循环p，但是当p大的时候就会TLE。然后就了解到了快速幂。 快速幂：顾名思义，快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N)，与朴素的O(N)相比效率有了极大的提高。不得不说，二进制是一个很神奇的东西任何一个正整数都能转换为二进制数（废话）由上可得，任何一个数都可转化为2a+2b+…+2m。例如7，...

【洛谷】P1226 快速幂（java）

北海_南风

09-29

305

编程改变世界 快速幂（ab）：它基于二分法的思想，因此也常被称为二分幂，快速幂基于以下事实：如果b是奇数，那么有ab = a * ab -1 如果b是偶数，那么有ab = a(b/2) * a(b/2)。显然，b是奇数的情况总是可以在下一步转换为b是偶数的情况，而b是偶数的情况总可在下一步转换为b/2的情况。这样，在 log(b) 级别次数的转换后，就可以把b变成0，而任何正整数的0次方都是1. 所以时间复杂度为O(logb) 代码如下： public static long bin(lo

洛谷 P3390 矩阵快速幂模板

syyer

09-26

338

题目背景矩阵快速幂 题目描述给定n*n的矩阵A，求A^k 输入输出格式输入格式：第一行，n,k 第2至n+1行，每行n个数，第i+1行第j个数表示矩阵第i行第j列的元素输出格式：输出A^k 共n行，每行n个数，第i行第j个数表示矩阵第i行第j列的元素，每个元素模10^9+7 输入输出样例输入样例#1： 2 1 1 1 1 1 输出样例#1： 1 1

随机数生成器洛谷P2044 矩阵快速幂

DaoCaoRen___的博客

02-27

505

题目描述栋栋最近迷上了随机算法，而随机数是生成随机算法的基础。栋栋准备使用线性同余法（Linear Congruential Method）来生成一个随机数列，这种方法需要设置四个非负整数参数m,a,c,X_0m,a,c,X0，按照下面的公式生成出一系列随机数\{X_n\}{Xn}： X_{n+1}=(aX_n +c)\bmod mXn+1=(aXn+c)modm 其中\bmod mmodm表示前面的数除以mm的余数。从这个式子可以看出，这个序列的下一个数总是由上一个数生成的。 ...