HDU1061_Rightmost Digit【快速幂取余】

浏览数：53 / 时间：2015年06月09日

Rightmost Digit

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 33161 Accepted Submission(s): 12696

Problem Description
Given a positive integer N, you should output the most right digit of N^N.

Input
The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.
Each test case contains a single positive integer N(1<=N<=1,000,000,000).

Output
For each test case, you should output the rightmost digit of N^N.

Sample Input
2
3
4

Sample Output
7
6

Hint
In the first case, 3 * 3 * 3 = 27, so the rightmost digit is 7.
In the second case, 4 * 4 * 4 * 4 = 256, so the rightmost digit is 6.

Author

Ignatius.L

题目大意：给你一个N，计算N^N个位上的数字是多少

思路：普通方法超时，利用快速幂取余计算N^N%10，这里贴一个二进制

快速幂取余的代码

#include<stdio.h>
#include<string.h>

__int64 QuickPow(__int64 a,__int64 p)
{
    __int64 r = 1,base = a;
    __int64 m = 10;
    while(p!=0)
    {
        if(p & 1)
            r = r * base % m;
        base = base * base % m;
        p >>= 1;
    }
    return r;
}
int main()
{
    __int64 N;
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%I64d",&N);
        __int64 ans = QuickPow(N,N);
        printf("%I64d\n",ans);
    }
    return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

HDU1061_Rightmost Digit【快速幂取余】