程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA 10515(求m^n的個位數)

UVA 10515(求m^n的個位數)

編輯:C++入門知識

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<

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved