快速幂

快速幂

时间： 1ms        内存：128M

描述：

给定一个整数N，求出N^N(N的N次方)的最后一位

输入：

输入包含T组样例

每一组输入一个整数N  N(1<=N<=1,000,000,000)

输出：

对于每一组样例输出N^N最后一位

示例输入：

2
3
4

示例输出：

7
6

提示：

参考答案（内存最优[1120]）：

#include<stdio.h>
long long pow(long long n);
int main()
{
 long long n,ans,i;
 int t;
 scanf("%d",&t);
 for(i=1;i<=t;i++)
 {
  scanf("%d",&n);
  ans=pow(n);
  printf("%d\n",ans);
 }
 return 0;
}
long long pow(long long n)
{
    long long d,base;
    d=1;base=n;
    while(n!=0)
    {
        if(n&1!=0)
            d=(d*base)%10;
        n>>=1;
        base=(base*base)%10;
    }
    return d;
}

参考答案（时间最优[2]）：

#include<stdio.h>
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int a,b;
        int k=1;
        scanf("%d",&a);
        b=a;
        a=a%10;
        while(b)
        {
            if(b&1)
                k=((k%10)*(a%10))%10;
            a=((a%10)*(a%10))%10;
            b>>=1;
        }
        printf("%d\n",k);
    }
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。