A hard puzzle

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

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

這道題給把我整的自閉了(´-ι_-｀)

一開始根本不知道快速冪的演算法，總是會TLE

（這是我之前寫的暴力代碼，直接起飛233333）

#include <stdio.h>

int main() {
    int a,b,t;
    while(scanf("%d%d",&a,&b) != EOF) {
    t=a;
    if(b > 1)
        for(int i=2; i <= b; i++) {
            t=t*a;
            t=t%10;
        }
    printf("%d\n",t);
    }
    return 0;
}

後來Dalao給我講了講快速冪，在迷茫之中終於搞懂了（順便來一句，快速冪真相）；
（以下為快速冪的大體解釋）

int ksm(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b & 1)
            ans=ans*a;
        a=a*a;
        b=b >> 1;
    }
    return ans;
}
/*
總體上來講就是化成二進位後用二分法思想將一個大冪次分解為若幹個小冪次：
'a^n=[(a)*（二進位最後一位）]*[(a^2)*（二進位倒數第二位）]*[(a^4)*（二進位倒數第三位）]*[(a^8)*（二進位倒數第四位）]*[(a^16)*（二進位倒數第四位）]*[(a^32)*······';
*/
  //程式運行以'a^13'為例：
  //'13'轉化二進位'1101';
**//位運算（等價於'a%2'）取二進位最後一位;
  //為'1',把二分開的項運算出來放入結果，否則只進行二分
  //位移（比如第一步'1 1 0 1'位移就相當於去掉二進位最後一位）'1 1 0 1';
  //                    ^                                 ^
  //返回**步進行，直到'b == 0';
  //據二分法，得'a^13=[(a^1)*1]*[(a^2)*0]*[(a^4)*1]*[a(a^8)*1]';

由快速冪可以得出題解（因為ans計算時要考慮溢出問題所以改用long long變數儲存）

樣例答案（剛剛接觸點c++，有點亂。。。）

#include <bits/stdc++.h>
using namespace std;

long long ksm(long long a,long long b)  //快速冪
{
    long long ans=1;
    while(b)
    {
        if(b & 1)
            ans=ans*a%10;
        a=a*a%10;
        b=b >> 1;
    }
    return ans;
}

int main()
{
    long long a,b;
    while(scanf("%lld%lld",&a,&b) != EOF)
        printf("%lld\n",ksm(a,b));
    return 0;
}

（ps：日後我會填補快速乘的坑 ~ ヾ(=･ω･=)o）