Rightmost Digit

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 33161    Accepted Submission(s): 12696

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

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.

 

Author

Ignatius.L

题目大意：给你一个N，计算N^N个位上的数字是多少

思路：普通方法超时，利用高速幂取余计算N^N%10，这里贴一个二进制

高速幂取余的代码

#include
     
      #include
      
       __int64 QuickPow(__int64 a,__int64 p){    __int64 r = 1,base = a;    __int64 m = 10;    while(p!=0)    {        if(p & 1)            r = r * base % m;        base = base * base % m;        p >>= 1;    }    return r;}int main(){    __int64 N;    int T;    scanf("%d",&T);    while(T--)    {        scanf("%I64d",&N);        __int64 ans = QuickPow(N,N);        printf("%I64d\n",ans);    }    return 0;}