HDOJ 1061 Rightmost Digit（快速幂求模）

Rightmost Digit

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 38422 Accepted Submission(s): 14473

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(log₂N)，与朴素的O(N)相比效率有了极大的提高。

原理：

以下以求a的b次方来介绍

把b转换成二进制数。

该二进制数第i位的权为

例如

11的二进制是1011

11 = 2³×1 + 2²×0 + 2¹×1 + 2º×1

因此，我们将a¹¹转化为算

代码实现：

1.快速幂模板：

<span style="color:#000000;">int pow3(int a,int b)
{
    int r=1,base=a;
    while(b!=0)
    {
         if(b&1)
         r*=base;
         base*=base;
         b>>=1;
    }
    return r;
}//快速幂模板 
</span>

2.快速幂求模模板：

<span style="color:#000000;">long long result(long long a,long long b,long long m)
{
    long long d,t;
    d=1;
    t=a;
    while (b>0)
    {
        if (b%2==1)
            d=(d*t)%m;
        b/=2;
        t=(t*t)%m;
    }
    return d;
}//快速幂求模算法模板 
</span>

此题为快速幂求模的模板题，代码如下：

<span style="color:#000000;">#include<iostream>
using namespace std;

long long pow(long long n)
{
	long long d,t;
	d=1;t=n;
	while(n>0)
	{
		if(n&1)
			d=(d*t)%10;
		n>>=1;
		t=(t*t)%10;
	}
	return d;
}

int main()
{
	long long n,ans;
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n;
		ans=pow(n);
		cout<<ans<<endl;
	}
	return 0;
}</span>

HDOJ 1061 Rightmost Digit（高速幂求模）

Rightmost Digit

相关推荐