hdu1061-Rightmost Digit(附20循環的規律解法和附快速冪簡單原理）

1.快速冪實現a^N
求3^999(a=3,N=999):3 ^ 999 = 3 * 3 * 3 * … * 3，直接乘要做998次乘法。
快速冪方法實質使用了二分法進行時間優化:
 tmp+   =   tmp-*    a-;
3 ^ 1  =    3*    1
3 ^ 2  = (3 ^ 1)* (3 ^ 1)
3 ^ 4  = (3 ^ 2) *(3 ^ 2)
…………
3 ^ 256 = (3 ^ 128) * (3 ^ 128)
3 ^ 512 = (3 ^ 256) * (3 ^ 256)
==>
3 ^ 999
= (3 ^ 512) * (3 ^ 256) * (3 ^ 128) * (3 ^ 64) * (3 ^ 32) * (3 ^ 4) * (3 ^ 2) * 3
只做16次乘法。
將999轉為2進制數：1111100111
1    1   1   1  1 0 0 1 1 1
512 256 128 64 32 0 0 4 2 1
各個位上的值即為需要進行乘積的標志。
 

[cpp] 
#include "stdio.h"  
#include "string.h"  
#include "stdlib.h"  
#include "math.h"  
#include "algorithm"  
#include "iostream"  
 
using namespace std; 
 
#define INT __int64  
int Pow( INT n ) 
{ 
    int temp = n % 10 ; 
    int ans = 1 ; 
    while( n ) 
    { 
        if( n % 2 == 1 ) 
        { 
            n-- ; 
            ans *= temp; 
            ans %= 10 ; 
        } 
        else 
        { 
            n /= 2 ; 
            temp *= temp ; 
            temp %= 10 ; 
        } 
        ans %= 10 ; 
    } 
    return ans ; 
}  
     
int main() 
{ 
    INT n ; 
    int Case ; 
    cin >> Case ; 
    while( Case-- ) 
    { 
        cin >> n ;  
        cout << Pow( n ) << endl ; 
    } 
    return 0; 
} 

#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#include "math.h"
#include "algorithm"
#include "iostream"

using namespace std;

#define INT __int64
int Pow( INT n )
{
 int temp = n % 10 ;
 int ans = 1 ;
 while( n )
 {
  if( n % 2 == 1 )
  {
   n-- ;
   ans *= temp;
   ans %= 10 ;
  }
  else
  {
   n /= 2 ;
   temp *= temp ;
   temp %= 10 ;
  }
  ans %= 10 ;
 }
 return ans ;
}
 
int main()
{
 INT n ;
 int Case ;
 cin >> Case ;
 while( Case-- )
 {
  cin >> n ;
  cout << Pow( n ) << endl ;
 }
 return 0;
}

下面是發現沒20個數據存在循環，之前沒有將num[ 0] 賦值為0 ,總是WA,還懷疑規律是不是錯了，但是突然發現20的倍數mod20會為0

[cpp] 
#include<iostream>  
#include<cstdio>  
#include<cmath>  
 
using namespace std;  
 
int main() 
{ 
    __int64 n ; 
    int a , b , num[ 50 ] ; 
    int i ; 
    num[ 0 ] = 0 ;  
    for(i = 1 ; i <= 20 ; i++ ) 
    { 
        a = i ; 
        b = 1 ; 
        while ( a-- ) 
        { 
            b = b * i % 10 ; 
        } 
        num[ i ] = b ; 
    } 
    int Case ; 
    cin >> Case; 
    { 
    while( Case-- ) 
    {    
        cin >> n ; 
        n = n % 20 ; 
    //  cout << n << endl ;  
        cout << num[ n ] << endl ; 
    } 
} 
    return 0 ; 
} 

#include<iostream>
#include<cstdio>
#include<cmath>

using namespace std;

int main()
{
 __int64 n ;
 int a , b , num[ 50 ] ;
 int i ;
 num[ 0 ] = 0 ;
 for(i = 1 ; i <= 20 ; i++ )
 {
  a = i ;
  b = 1 ;
  while ( a-- )
  {
   b = b * i % 10 ;
  }
  num[ i ] = b ;
 }
 int Case ;
 cin >> Case;
 {
 while( Case-- )
 { 
  cin >> n ;
  n = n % 20 ;
 // cout << n << endl ;
  cout << num[ n ] << endl ;
 }
}
 return 0 ;
}