CCF NOI1037 个位数

问题链接：CCF NOI1037 个位数。

---

时间限制: 1000 ms  空间限制: 262144 KB

题目描述

  计算a^b的个位数。

输入

  一行两个空格隔开的正整数表示a和b。

输出

  输出a^b的个位数。

样例输入

2 4

样例输出

6

数据范围限制

  1<=a,b<=100000

---

问题分析

  这是一个计算a的b次方取其个位的问题。

  正解是采用快速模幂运算来实现，计算速度上要比其他方法快。

  “输出a^b的个位数”不如说“输出a^b的个位”好懂。原题这类含糊的问题太多了。

程序说明

  函数powermod()实现快速模幂计算。

要点详解

• 一般而言，用位运算代替除法，用移位运算代替除以2运算，运算速度上相对快一些。
• 能够使用复合运算符时，要尽量使用复合运算符。
  

---

参考链接：乘方取模计算（模幂计算）。

---

100分通过的C语言程序：

#include <stdio.h>

#define MOD 10

// 快速模幂计算函数
int powermod(int a, int n, int m)
{
    int res = 1L;
    while(n) {
        if(n & 1L) {
            res *= a;
            res %= m;
        }
        a *= a;
        a %= m;
        n >>= 1;
    }
    return res;
}

int main(void)
{
    int a, b;

    scanf("%d%d", &a, &b);

    printf("%d
", powermod(a, b, MOD));

    return 0;
}