求个位数

输入一个整数 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;
}