HDOJ1061 Rightmost Digit

Rightmost Digit

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 60576    Accepted Submission(s): 22770

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

Hint

阶乘是指数级增长的，N(1<=N<=1,000,000,000)那么大的数肯定不能直接算。

通过输出前面一百个来观察，很容易就得知这是有规律的。

规律就是每20个一次循环，建一个长度为20的数组存放这些数就OK。

import java.util.Scanner;

public class Main{
  private static Scanner scanner;
  private static int arr[];

  public static void main(String[] args) {
    dabiao();
    scanner = new Scanner(System.in);
    int cases = scanner.nextInt();
    while (cases-- > 0) {
      int n = scanner.nextInt();
      int res = n % 20;
      System.out.println(arr[res]);
    }
  }

  private static void dabiao() {
    arr = new int[20];
    for (int n = 0; n < arr.length; n++) {
      int res = n % 10;
      int y = res;
      for (int i = 1; i < n; i++) {
        res *= y;
        res %= 10;
      }
      arr[n] = res;
      // System.out.println(arr[n]);
    }
  }
}