HDU1061

题目链接

传送门

解题思路

涉及到快速幂算法,又要用到离散数学和数论的公式。
a^b mod c = ( (a mod c)(b mod c)) mod c,即a的b次幂对c求余等价于a对c求余乘以b对c求余的结果;
本题求n^n mod 10,等价于((n mod 10)
(n mod 10)) mod 10;
中间调用递归不断的对n值进行缩小;
当n为奇数时,相对于偶数多乘了一次本身对10的求余;

参考代码

#include <stdio.h>
int f(int k,int m)
{
    int t;
    if(m==0)
        return 0;
    if(m==1)
        return k;
    t=f(k,m/2);
    t*=t;
    if(m%2==1)
        t*=k;
    return t%10;
}

int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int m;
        scanf("%d",&m);
        printf("%d\n",f(m%10,m));
    }
    return 0;
}