hdu 1061 Rightmost Digit

缘起

就是给你一个正整数N, 求 N^N 的个位数字

分析

题意很裸

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
给定正整数N，您应该输出N^N的最右边数字。

【输入】
输入包含几个测试用例。 输入的第一行是单个整数T，它是测试用例的数量。 
每个测试用例包含一个正整数N（1 <= N <= 1,000,000,000）。

【输出】
对于每个测试用例，您应该输出N ^ N的最右边的数字。

【样例输入】
2
3
4

【样例输出】
7
6

【限制】
Time limit 1000 ms
Memory limit 32768 kB

因为个位数字其实和高位无关. 为了保证不超时，显然要使用快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include "stdafx.h"

#include <stdio.h>
#include <math.h>
#define LOCAL
typedef long long LL;

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	LL n, tt;
	scanf("%lld", &tt);
	while(tt--)
	{
		scanf("%lld", &n);
		int t = n%10,ans=1; // 最初的个位数字
		while(n) // 快速幂
		{
			if (n&1)
			{
				ans = ans *t %10;
			}
			if (n>1)
			{
				t = t*t%10;
			}
			n>>=1;
		}
		printf("%d\n", ans);
	}
	return 0;
}

ac情况

30151717 2019-08-07 14:12:13 Accepted 1061 0MS 1204K 460 B G++ yfsyfsyfs