求一个数n次方后的末尾数（数论/快速幂）

如何快速求出一个数n次方后的末尾数为多少

问题描述

hdu1061-Rightmost Digit
hdu1097-A hard puzzle
这两个oj题目思路几乎一样，都是为了快速求出一个数n次方后的末尾数为多少？

解题思路

1的所有次方都是1
0的所有次方都是0
5的所有次方都是5
6的所有次方都是6
2^1=2 2^2=4 2^3=8 2^4=6(四个一循环)
3^1=3 3^2=9 3^3=7 3^4=1(四个一循环)
7^1=7 7^2=9 7^3=3 7^4=1(四个一循环)
4^1=4 4^2=6(两个一循环)
8^1=8 8^2=4(两个一循环)
9^1=9 9^2=1(两个一循环)

代码实现

下面以hdu1097-A hard puzzle为例

• 代码1（自己写的傻乎乎）

  #include<iostream>
  using namespace std;
  int main(){
      int m,n,last;
  
      while(cin>>m>>n){
          last=m%10;
          if(last==0||last==1||last==5||last==6){
              cout<<last<<endl;
          }else if(last==4){
              if(n%2==1){
                  cout<<4<<endl;
              }
              if(n%2==0){
                  cout<<6<<endl;
              }
          }else if(last==9){
              if(n%2==1){
                  cout<<9<<endl;
              }
              if(n%2==0){
                  cout<<1<<endl;
              }
          }else if(last==2){
              if(n%4==1){
                  cout<<2<<endl;
              }
              if(n%4==2){
                  cout<<4<<endl;
              }
              if(n%4==3){
                  cout<<8<<endl;
              }
              if(n%4==0){
                  cout<<6<<endl;
              }
          }else if(last==3){
              if(n%4==1){
                  cout<<3<<endl;
              }
              if(n%4==2){
                  cout<<9<<endl;
              }
              if(n%4==3){
                  cout<<7<<endl;
              }
              if(n%4==0){
                  cout<<1<<endl;
              }
          }else if(last==7){
              if(n%4==1){
                  cout<<7<<endl;
              }
              if(n%4==2){
                  cout<<9<<endl;
              }
              if(n%4==3){
                  cout<<3<<endl;
              }
              if(n%4==0){
                  cout<<1<<endl;
              }
          }else if(last==8){
              if(n%4==1){
                  cout<<8<<endl;
              }
              if(n%4==2){
                  cout<<4<<endl;
              }
              if(n%4==3){
                  cout<<2<<endl;
              }
              if(n%4==0){
                  cout<<6<<endl;
              }
          }
      }
      return 0;
  }
  
  `

• 代码2

  #include <stdio.h>
  #include <math.h>
  
  int main() {
      int a[10] = {1, 1, 4, 4, 2, 1, 1, 4, 4, 2};
      int n, num, rmd, ans; // rmd = rightmost digit
      scanf("%d", &n);
      for (int i = 0; i < n; ++i) {
          scanf("%d", &num);
          rmd = num % 10;
          ans = (int) pow(rmd, num % a[rmd] ? num % a[rmd] : a[rmd]);
          printf("%d\n", ans % 10);
      }
  }

• 代码3

  #include<iostream>//1097
  #include<algorithm>
  using namespace std;
  int main()
  {    int a,b,c[4];
    while(cin>>a>>b)
    {
        a=a%10;
        c[0]=a;//一次方的末尾数
       c[1]=(c[0]*a)%10;//二次方的末尾数
       c[2]=(c[1]*a)%10;//三次方的末尾数
       c[3]=(c[2]*a)%10;//四次方的末尾数
       if(b%4==1)
           cout<<c[0]<<endl;
       if(b%4==2)
           cout<<c[1]<<endl;
       if(b%4==3)
           cout<<c[2]<<endl;
       if(b%4==0)
           cout<<c[3]<<endl;
    }
    return 0;
  }

运行结果

参考

ACM — Rightmost Digit
A hard puzzle