求一个数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;
    }
    
我来评几句
登录后评论

已发表评论数()