HDU 1061 Rightmost Digit（n的n次方的个位数）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1061

题意很简单，，就是求n的n次方的末位数字，常见做法有两种：

1.快速幂取模

2.打表找规律

我采用第一种做法。不过我直接套了个整数超大次幂取模的模板，用了欧拉降幂处理指数 。当然对于这道题主要运用了快速幂取模，毕竟指数不够大

//A^B %C=A^( B%phi(C)+phi(C) ) %C
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <iostream>
#include<string>
#include<cmath>
using namespace std;
typedef long long LL;
int phi(int x)
{
    int i,j;
    int num = x;
    for(i = 2; i*i <= x; i++)
    {
        if(x % i == 0)
        {
            num = (num/i)*(i-1);
            while(x % i == 0)
            {
                x = x / i;
            }
        }
    }
    if(x != 1)
        num = (num/x)*(x-1);
    return num;
}
LL quickpow(LL m,LL n,LL  k)
{
    LL ans=1;
    while(n)
    {
        if(n&1)
            ans=(ans*m)%k;
        n=(n>>1);
        m=(m*m)%k;
    }
    return ans;
}
char tb[1000015];
int main()
{
    LL a,nb;
    int c,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",tb);
        sscanf(tb,"%lld",&a);
        c=10;
        int PHI=phi(c);
        LL res=0;
        for(int i=0; tb[i]; i++)
        {
            res=(res*10+tb[i]-'0');
            if(res>c)
                break;
        }
        if(res<=PHI)
        {
            printf("%lld\n",quickpow(a,res,c));
        }
        else
        {
            res=0;
            for(int i=0; tb[i]; i++)
            {
                res=(res*10+tb[i]-'0')%PHI;
            }
            printf("%lld\n",quickpow(a,res+PHI,c));
        }
    }
    return 0;
}