【快速幂】【水】Rightmost Digit

凡凡说:“我的数学,那是天下无敌,你们一个能打的都没有!” 凉凉听了,很不服气:“那我要考考你,N个N相乘的最后一位数字是多少?

输入

输入包含多组测试数据。输入的第一行是单个整数 T,表示测试数据的组数。接下来是 T 组测试数据。

每组测试数据,包含单个正整数 N (1 <= N <= 1,000,000,000)。

输出

对于每组测试数据,请输出 N^N 的最右一位数字。

示例输入

2
3
4

示例输出

7
6

提示

在第一组测试数据中,3 * 3 * 3 = 27,因此最右一位数字是 7。
在第二组测试数据中,4 * 4 * 4 * 4 = 256,因此最后一位数字是 6。

思路

标准的快速幂题目,注意数据类型和溢出的问题。

import java.util.Scanner;
public class HDU1061 {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int T = Integer.parseInt(in.nextLine());
        while (T-- > 0){
            long N = Long.parseLong(in.nextLine());
            long p = N;
            long r = 1;
            while (p > 0){
                // 当p为奇数时多乘一次
                if(p % 2 == 1){
                    r = (r * N) % 10;
                }
                // 计算过程中取模防止溢出
                N = (N * N) % 10;
                p /= 2;
            }
            System.out.println(r);
        }
    }
}
上一篇:单例模式


下一篇:Practical Training JQuery.Ajax