题目大意：给定数字n(1<=n<=1,000,000,000),求n^n%10的结果
解题思路：首先n可以很大，直接累积n^n再求模肯定是不可取的，
因为会超出数据范围，即使是long long也无法存储。
因此需要利用 (a*b)%c = (a%c)*(b%c)%c,一直乘下去,即 (a^n)%c = ((a%c)^n)%c;
即每次都对结果取模一次
此外，此题直接使用朴素的O(n)算法会超时，因此需要优化时间复杂度：
一是利用分治法的思想，先算出t = a^(n/2)，若n为奇数，则返回t*t*a,偶数则返回t*t;
二是使用通过循环实现快速幂取模(其实二者实质上是相同的)。
1.递归解法
/* HDU 1061 Rightmost Digit --- 快速幂取模 */
#include <cstdio> /*
@function: 计算n^n%10
@param: n为待计算的数
@return: 返回n^n%10的结果
@explain: 利用分治策略以及同余定理实现快速幂取模
*/
int pow_mod(int a, int n){
if (n == ){
return ;
}
int x = pow_mod(a, n / ); //x = a^(n/2)
long long ans = (long long)x * x % ;
if (n & ){
//若n为奇数
ans = ans * a % ;
}
return (int)ans;
} int main()
{
int t, n;
scanf("%d", &t);
while (t--){
scanf("%d", &n);
printf("%d\n", pow_mod(n, n));
} return ;
}
2.快速幂取模
/* HDU 1061 Rightmost Digit --- 快速幂取模 */
#include <cstdio> /* 快速幂取模 */
int pow_mod(int a, int n){
int ans = ;
int t = a % ;
while (n){
if (n & ){
//n为奇数
ans = ans * t % ;
}
n /= ; //相当于将n拆成相应的二进制
t = t * t % ;
}
return ans; } int main()
{
int t, n;
scanf("%d", &t);
while (t--){
scanf("%d", &n);
printf("%d\n", pow_mod(n, n));
} return ;
}