这题是一道关于快速幂算法的题目,这道题有很多种解题方法,好像找规律也行,不过我在这里不打算讲找规律的方法(我也没找过),我主要是讲一下利用二进制来实现快速幂的方法。
例如:求a^b(不考虑超范围的问题)。先把b按二进制展开,即b=bn*2^n+......+b1*2^1+b0*2^0,所以a^b=a^(bn*2^n+......+b1*2^1+b0*2^0) =a^(bn*2^n)*......*a^(b1*2^1)*a^(b0*2^0),其中bi取值为0和1,两个乘数之间的大小事平方的关系。利用这个思想就可以在log2(n)的时间复杂度内解决问题。
理解了上述这些,这道题目就没问题了。
(下面所谓二进制法和二分法是我凭感觉随便写的名字,大家别被我误导了,如果有人知道到底该怎么叫,请麻烦告诉我一下!)
代码1(G++)(二进制法):
#include <cstdlib> #include <iostream> using namespace std; int quick_pow(int a,int b) { int ans=1; a%=10; while(b) { if(b&1) ans=a*ans%10; b>>=1; a=a*a%10; } return ans; } int main(int argc, char *argv[]) { int t,n; cin>>t; while(t--) { cin>>n; cout<<quick_pow(n,n)<<endl; } system("PAUSE"); return EXIT_SUCCESS; }
代码2(G++)(二分法):
#include <cstdlib> #include <iostream> using namespace std; int func(int a,int b) { int tmp; if(b==1) return a%10; else{ tmp=func(a,b/2); if(b%2==0) return tmp*tmp%10; else return tmp*tmp*a%10; } } int main(int argc, char *argv[]) { int t,n; cin>>t; while(t--) { cin>>n; cout<<func(n%10,n)<<endl; } system("PAUSE"); return EXIT_SUCCESS; }
顺便说一句,发现在杭电同一份代码交两次,显示的时间不同,不知是意外还是其他什么情况。
题目:
Rightmost Digit
Time Limit: 2000/1000 MS (Java/Others) Memory Limit:
65536/32768 K (Java/Others)
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).
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 6HintIn 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.