欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU-1061 Rightmost Digit(快速幂)

程序员文章站 2022-06-04 19:39:13
...

原题链接: http://acm.hdu.edu.cn/showproblem.php?pid=1061

HDU-1061 Rightmost Digit(快速幂)
测试样例

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