问题描述

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; 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; c[0]=a;//一次方的末尾数 c[1]=(c[0]*a);//二次方的末尾数 c[2]=(c[1]*a);//三次方的末尾数 c[3]=(c[2]*a);//四次方的末尾数 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