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 <bits/stdc++.h>
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<<ans%10<<endl;
    }
    return 0;
}

    原文作者:AC_XXZ
    原文地址: https://blog.csdn.net/u013445530/article/details/46640509
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞