UVA 10515（求m^n的個位數）

UVA 10515（求m^n的個位數）

題意:給出兩個正整數m,n(0<=m,n<=10^101)，求m^n的最後一位數

思路：找規律，對於m的話只需考慮個位數就行，個位數不會因相乘的進位而發生變化，對於指數n打表發現2,3,7，8都是以每四個連續次方一個循環，4和9以2為循環

所以

取m的最後一位k，n取最後兩位d(判斷正整數能否整除4取最後兩位就行，很好證明),m^n的的最後一位數字為:

ans = (k^p)%10

p = d%4 == 0 ? 4 : d%4;

擴展知識點:

如何判斷一個非常大的數n（超出long long）能否被一個很小的m整除?

遞推:\

S[0] = 0;

S[i] = (S[i-1]*10 + a[i]) % m;

最後判斷S[n.length-1]是否等於0即可

#include 
using namespace std;

int main()
{
#ifdef xxz
   // freopen("in","r",stdin);
#endif // xxz
    string m, n;
    while(cin>>m>>n,m+n != "00")
    {
        int k = m[m.length()-1] - '0';
        int d = ( n.length() == 1 ? n[0] : n[n.length() - 2]*10 + n[n.length()-1] ) - '0';
        int p = d%4 == 0 ? 4 : d%4;
        int ans = pow(k,p);
        cout<