输入一个整数 n ，求 nn 的个位数是多少。
输入格式
一个整数： n
输出格式
输出格式：个位数（0 – 9中的数）
数据范围
1 <= n <= 109
输入样例
9
输出样例
9
思路：按照正常思路求解，导入math模块 pow(n,n)。
不妨了解一下快速幂算法。
模运算性质
快速幂算法
可以分解为
注意此时指数为奇数 奇数时需要分出一个底数
然后 可以看到 当指数为偶数 可以将底数合并起来
这就是快速幂的思路 奇数拆 偶数合 降低时间复杂度
#include<stdio.h>
//#include<math.h>
int ges(int num);
int main() {
//clock_t为CPU时钟计时单元数
int n = 9;
printf("ges():%d \n",ges(n));
return 0;
}
int ges(int num) {
int base = num;
int pow = num;
int result = 1;
while(pow>0) {
if(pow%2 & 1 == 1) { // 奇数
result = result * base % 10;
}
pow >>= 1; //位运算 右移等于除以2
base = (base*base)%10;
}
return result;
}
