快速幂

Problem Description

Given a positive integer N, you should output the most right digit of N^N.

Input

The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.
Each test case contains a single positive integer N(1<=N<=1,000,000,000).

Output

For each test case, you should output the rightmost digit of N^N.

Sample Input

2
3
4

Sample Output

7
6

刚开始想着变乘边取模(%10)发现依然tle,然后想到新学的快速幂

快速幂:计算a^b%p(时间复杂度o(log2b))

利用正数肯定能唯一表示为若干指数不重复的2次幂的和。

例如b=5=1×(2^2)+0×(2^1)+1×(2^0),a=3

所以3^5=3^(1×(2^2))×3^(0×(2^1))×3^(1×(2^0));等式右边相邻两项是平方关系

用(b&1)可以表示b二进制的最后一位,对应上式中的0,1,只要在1的时候,把乘积项累积到答案中,而b>>1运算可以舍去最低位,在递推的过程中两者结合,即可遍历b在二进制表示下的所有位数

AC代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
#define p 10;
int main()
{	long long a,b;
	int n;
	cin>>n;
	while(n--)
	{
		cin>>a;
	{	 b=a;
		long long ans=1;
		for(;b;b=b>>1)
		{	if(b&1) ans=ans*a%p; 
			a=a*a%p;
		}
		cout<<ans<<endl;
	}
	}
	
return 0;	
}