C/C++：计算N的N次方的个位数（巧用快速幂与模运算性质）_用c++计算n的n次方-程序员宅基地
题目描述（源自杭电OJ）：
相关数学知识一：取模运算的性质
a乘b的结果对p取模等于a对p取模的结果乘b对p取模的结果再整体取模于p，详见下图
证明过程如下：
相关数学知识二：快速幂运算
以求a的b次方为例，由于要乘b次a，此时的时间复杂度为O（b）；如果要求a的的平方的b/2次（如果b是奇数，要再乘一个底数a），也就转化为a的4次方的b/4次，以此类推，直到b=1时，这样转化的次数为log以2为底的b的对数，转化结束。这样做，时间复杂度从O（b）变成了O（log以2为底的b的对数），运算次数实现了指数级的减小。
例如，我们计算3的10次方，最快的算法应该是，转化成9的5次方，转化成81的平方再乘9，得出最终结果。这个算法比起原始算法，如果都用for循环，就形成了循环10次和循环4次的差别，循环次数越少，时间复杂度越低，越不容易时间超限。
本题分析——“快速幂运算”与“取模运算性质” 的巧妙结合
求N的N次方的个位数，N还可以大到1,000,000,000。从数据范围来说，N的N次方这个数的最大值（1,000,000,000的1,000,000,000次方）本身来说，它完全超过了long long（24位）可以承载的最大范围，数据会溢出；从时间复杂度来说，要算N的N次方这个数的最大值，需要1,000,000,000次循环，运行时间也会超限。因此，我们从两个方面着手，解决这个问题。
第一步，解决数据溢出问题，我们利用到“取模运算的性质”，求N的N次方的个位数，其实也就是(N*N*N*...*N（共N个））%10，利用“取模运算的性质”，则可以转化为(（（（N%10）*N%10）*N%10）*N%10）*N%10......【从最内部的括号算往外算，算N次】。这样，数据范围最大也就一开始的1,000,000,000，此后的数据，都是个位数字之间的运算（原理：对10取模的一切数字只可能是个位数0~9），不可能再溢出，也就是说，我们控制住了数据范围，做到第一步。
第二步，解决时间复杂度问题，我们利用“快速幂运算”算法知识，①求N的N次幂，根据指数运算的性质，②就是求N的平方的N/2次幂，③也就是求N的4次方的N/4次幂，...，直到N的N次方的N/N次也就是1次幂，从①→②→③一直到最后，转化的步骤我们一共做了log以2为底的N次，而log以2位底的1,000,000,000次的结果大约在25左右，根据单调性，最多只用转化25次，时间复杂度大大降低，时间复杂度问题解决了。（当然要考虑N为奇数的情况，当N为奇数的时候，我们多乘一次底数N即可解决该问题，在代码中利用if语句实现）。
第三步，结合第一步与第二步，拟出基本思路，写出最终程序代码。
第一次：将求N的N次的个位数，转化为求N的平方模10的N/2次幂（如果N为奇数，先将结果多乘一个底数N）。
第二次：求N的平方模10的N/2次幂，转化为求（N的平方模10的结果）的平方模10的N/4次幂（同样，如果N为奇数，先将结果多乘一个底数N）。
以此类推............
第log以2为底的N次：求得最终的N的N次方的个位数。
代码实现（C++）：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll Pow(ll a, ll b) //利用快速幂算法+取模运算性质，剧减数据范围与时间复杂度
{
int ans=1;
a%=10;
while(b)
{
if(b&1)ans=ans*a%10; //b&1用于判断b的奇偶性，相较于b%2==1，效率更高
a=a*a%10;
b>>=1; //b>>=1用于对b整除2，相较于b/=2，效率更高
}
return ans;
}
int main()
{
int t;
cin>>t;
ll n;
while(t--)
{
cin>>n;
cout<<Pow(n,n)<<endl;
}
return 0;
}
运行结果展示：
参考资料：
https://www.bilibili.com/video/BV12r4y1w7tx?from=search&seid=11692212080769773182
PS:第一次做博客，可能会有许多疏忽，望大佬指正，也希望能点赞得到鼓励~~
智能推荐
【WebApi】————.net WebApi开发（一）_webapi .net-程序员宅基地
文章浏览阅读8.5k次。【1】.部署环境.net4及以上版本。【2】.vs2010 开发需单独安装vs2010 sp1和mvc4mvc4：http://www.asp.net/mvc/mvc4【3】.开发1.新建项目选择ASP.net MVC 4 Web应用程序2.选择Web API 3.在新建立的项目里面有已经生成的webapi模版其中App_Start文件夹下WebApiCo..._webapi .net
几招教你阻止百度搜索自动跳转百度APP（其他网站也适用）！_百度自动跳转app怎么解决-程序员宅基地
文章浏览阅读10w+次，点赞15次，收藏33次。最近阿虚看到个消息说「百度」发布了新政策，禁止网站通过搜索引擎打开后折叠内容强迫下载APP客户端听起来似乎是百度难得良心一回？但实际上该政策仅限于手机百度APP内如果你是通过浏览器用百度搜索则与新政策完全没关系正好前不久不少粉丝来问过我这样一个问题：怎么屏蔽手机浏览器上的「跳转某某APP打开查看」提示那今天阿虚就来教一下怎么解决吧，毕竟这东西的确是有点烦人…屏蔽「跳转某某APP打开查看」这个问题我细看了下，还得分俩类：文章只能显示部分，然后提示你需要安装APP才能查看的，这种应该是大_百度自动跳转app怎么解决
PHP快速入门12-异常处理，自定义异常、抛出异常、断言异常等示例_php 抛出异常-程序员宅基地
文章浏览阅读843次。PHP的异常处理机制可以帮助我们在程序运行时遇到错误或异常情况时，及时发出警告并停止程序继续运行。下面是10个例子，分别展示了PHP异常处理的不同用法。_php 抛出异常
linux 清空docker容器日志_linux清理docker容器log-程序员宅基地
文章浏览阅读221次。【代码】linux 清空docker容器日志。_linux清理docker容器log
青岛大学开源OJ平台搭建_github oj开源-程序员宅基地
文章浏览阅读7.3k次，点赞3次，收藏15次。源码地址为:https://github.com/QingdaoU/OnlineJudge可参考的文档为:https://github.com/QingdaoU/OnlineJudgeDeploy/tree/2.0一、安装所依赖的环境sudo apt-get update && sudo apt-get install -y vim python-pip curl g..._github oj开源
浅谈数据安全-程序员宅基地
文章浏览阅读4.4k次。在《网络安全法》中，虽然已经明确了要求保障网络数据的完整性、保密性、可用性的能力，但随着近些年数据安全热点事件的出现，如数据泄露事件、个人信息滥用事件。表明对数据保护的要求仅依赖《网络安全法》中的几款条例是不足以支撑的。因此2021年9月1日《中华人民共和国数据安全法》便正式诞生，从此数据安全也被推上了风口浪尖。那么数据安全如何定义？与传统网络安全有何区别？数据安全体系又应该如何建立？..._数据安全
随便推点
联想笔记本G510升级固态硬盘(SSD)血泪教程!!!_联想g510更换固态硬盘-程序员宅基地
文章浏览阅读8.5w次，点赞23次，收藏55次。#联想笔记本G510升级固态硬盘(SSD)血泪教程!!!用了5年的联想笔记本G510,经过了四年的游戏历程,然后四年后还老当益壮的挣扎在我工作的战斗一线,是我并肩作战多年,比兄弟还要亲的兄弟,虽然此时已经身躯残破,反应迟缓我依旧不舍得抛弃它(主要是没钱!)然后为了我个人的用户体验决定花少量的票子,让它多挣扎一会,最好是能坚持到我度过贫困期. 下面是我升级的悲催历程! - 首先为了提升运行速..._联想g510更换固态硬盘
问题记录——正则表达式匹配控制符_正则表达式匹配控制字符-程序员宅基地
文章浏览阅读910次。问题前端用xterm.js通过websocket连接docker虚拟终端，返回的字符中包括如下字符串，其中有两个控制字符，“ESC"和"BEL” ，想通过正则表达式匹配这一段字符，然后去掉这段字符:参考文档控制字符编码表转义符对照表通过上面查询得知，"ESC"和"BEL"这两个控制符的ASCII码分别为：十进制为27和7，十六进制为0x1B和0x07，转义符分别为：\e和\a代码**注意：**直接使用ASCII码匹配是不行的，一定要用转义符才行。如下测试代码中，只有regex3才能匹_正则表达式匹配控制字符
Android RIL框架分析-程序员宅基地
文章浏览阅读1.5k次。1.RIL框架 RIL，Radio Interface Layer。本层为一个协议转换层，提供Android Telephony与无线通信设备之间的抽象层。 Android RIL位于Telephony Frameworks之下，Modem之上的，根据源码，RIL可以分为两个部分:Frameworks 框架层中的java程序，简称RILJ。HAL层中C/C++程序，简称RILC，RILC具体的又包括LibRIL、Rild和Reference-RIL这三个部分。 Andr..._ril框架
Python编程基础：第六节 math包的基础使用Math Functions_ps math function-程序员宅基地
文章浏览阅读565次。第六节 math包的基础使用前言实践前言我们通常会对数值型变量进行计算，这里我们给出一些常用的函数用于辅助你的计算过程。常用的数学计算函数均在math包。实践首先我们导入math包，并定义一个浮点型变量pi将其赋值为3.14：import mathpi = 3.14如果我们需要计算浮点型变量四舍五入后的计算结果，用函数round()即可：print(round(pi))>>> 3如果我们需要向上取整，那就需要函数math.ceil()：print(math.cei_ps math function
canal异常 Could not find first log file name in binary log index file_canal could not find first log file name in binary-程序员宅基地
文章浏览阅读4.4k次，点赞3次，收藏2次。Could not find first log file name in binary log index file问题解决解决过程问题最近在使用canal来监测数据库的变化，处理变动的数据。由于有一段时间没有用了，这次启动在日志文件中看到这个异常 Could not find first log file name in binary log index file，详细信息如下：2020-12-16 19:14:42.053 [destination = tradeAndRefund , addr_canal could not find first log file name in binary log index file
【练习】生成10个1到20之间的不重复的随机数并降序输出-程序员宅基地
文章浏览阅读960次。分析：1.创建一个Random对象；2.创建一个hashset的集合对象；3.循环生成10个1-20的随机数4.输出。package edu.xalead;import java.util.*;public class Test { public static void main(String[] args) { Random r...