HDU_1061:Rightmost Digit

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.

最先想到的是一个一个算，但是由于数据范围太大，O(n^2)的时间复杂度对于n = 10亿时，10亿^10亿次乘法运算实在是不能忍受的。因此下面的程序超时(Time Limit Exceeded)。

#include<stdio.h>

int main(void)

{

    int cases, n, copy_n, result;

    scanf("%d", &cases);

    while(cases--)

    {

        scanf("%d", &n);

        copy_n = n;

        n = n%;

        result = ;

        while(copy_n--)

        {

            result = (result*n)%;

        }

        printf("%d\n", result);

    }

    return ;

}

下面，快速幂一来就AC了：

#include<stdio.h>

int my_power(int m, int n); // 求m的n次方的尾数

int main(void)

{

    int cases, n;

    scanf("%d", &cases);

    while(cases--)

    {

        scanf("%d", &n);

        printf("%d\n", my_power(n, n));

    }

    return ;

}

int my_power(int m, int n)

{

    m = m%;

    if(n == )

        return m;

    if(n% == )

        return ( my_power(m*m, n/) ) % ;

    else

        return ( my_power(m*m, n/)*m ) % ;

}

可以看到，快速幂的时间复杂度是O(logn)，n = 10亿时，大约32次递归调用就能出结果，效率极大的提高了。

巴特西

HDU_1061:Rightmost Digit

最新文章

热门文章