HDOJ 1097 A hard puzzle

A hard puzzle

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

Total Submission(s): 21601    Accepted Submission(s): 7594

Problem Description lcy gives a hard puzzle to feng5166,lwg,JGShining and Ignatius: gave a and b,how to know the a^b.everybody objects to this BT problem,so lcy makes the problem easier than begin.

this puzzle describes that: gave a and b,how to know the a^b's the last digit number.But everybody is too lazy to slove this problem,so they remit to you who is wise.

Input There are mutiple test cases. Each test cases consists of two numbers a and b(0<a,b<=2^30)

Output For each test case, you should output the a^b's last digit number.

Sample Input

7 66
8 800
        

Sample Output

9
6
        

Author eddy  

Recommend JGShining  

首先...裸算必然TLE.我不信邪的試了下

//喜聞樂見的TLE 
#include <iostream>
using namespace std;
int main(int argc, char *argv[])
{
    int a,b,i,s;
     while (cin>>a>>b){
         s=a%10;
         for(i=1;i<b;++i){
             s*=a;
             s%=10;
         }
         cout<<s<<endl;
     }
    return 0;
}
           

以前學過快速幂的說,回想了下便有了第二個代碼(快速幂算法自行百度)

//快速幂 
#include <iostream>
using namespace std;
int qm(int a,int b){
    int s;
    if (b==1) return a;
    s=qm(a,b/2); s*=s;
    if (b%2==1) s*=a;
    return s%10; 
}
int main(int argc, char *argv[])
{
    int a,b,i,s;
     while (cin>>a>>b){
         cout<<qm(a%10,b)<<endl;
     }
    return 0;
}
           

到這裡已經AC了,還用到了算法,可是.解法不是最優. 一位整數的n次方是有規律可循的....我就不說什麼了

//隻讓答最後一位，找規律顯然最簡單，時間複雜度最優。數學規律，最簡解決之道。 
#include <iostream>
using namespace std;
int main(int argc, char *argv[])
{
   int result[10][5]={{0,0,0,0,0},{0,1,1,1,1},
                      {0,2,4,8,6},{0,3,9,7,1},
                      {0,4,6,4,6},{0,5,5,5,5},
                      {0,6,6,6,6},{0,7,9,3,1},
                      {0,8,4,2,6},{0,9,1,9,1}};
   int a,b;
   while(cin>>a>>b){
           a%=10;
           cout<<result[a][b%4==0?4:b%4]<<endl;
   }
    return 0;
}
           

kdwycz的網站：  http://kdwycz.com/

kdwyz的刷題空間：http://blog.csdn.net/kdwycz