HDU-1061 Rightmost Digit(快速幂)
程序员文章站
2022-06-04 19:39:13
...
原题链接: http://acm.hdu.edu.cn/showproblem.php?pid=1061
测试样例
Sample Input
2
3
4
Sample Output
7
6
Hint
In the first case, 3 * 3 * 3 = 27, so the rightmost digit is 7. In the second case, 4 * 4 * 4 * 4 = 256, so the rightmost digit is 6.
题意: 求 N N N^N NN最右边的数字。
解题思路: 我们知道数字对10取余自然可以得到最右边的数字。所以这道题相当于隐含告诉你我们要取余多少了,直接平方是不可能的,算是快速幂模板题吧。
AC代码
/*
*邮箱:aaa@qq.com
*blog:https://me.csdn.net/hzf0701
*注:文章若有任何问题请私信我或评论区留言,谢谢支持。
*
*/
#include<bits/stdc++.h>//POJ不支持
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=a;i>=n;i--)
using namespace std;
const int inf=0x3f3f3f3f;//无穷大。
const int maxn=1e5;//限定值。
typedef long long ll;
ll t,n;
ll quick(ll n,ll m){
if(m==1){
return n%10;
}
else if(m%2==0){
return quick(n*n%10,m/2)%10;
}
else{
return quick(n*n%10,m/2)*n%10;
}
}
int main(){
while(cin>>t){
while(t--){
cin>>n;
cout<<quick(n,n)<<endl;
}
}
return 0;
}