HDU2035（附所用数论中的性质推导及快速模运算的递归形式）

Problem Description
求A^B的最后三位数表示的整数。
说明：A^B的含义是“A的B次方”

Input
输入数据包含多个测试实例，每个实例占一行，由两个正整数A和B组成（1<=A,B<=10000），如果A=0, B=0，则表示输入数据的结束，不做处理。

Output
对于每个测试实例，请输出A^B的最后三位表示的整数，每个输出占一行。

Sample Input
2 3
12 6
6789 10000
0 0

Sample Output
8
984
1

如下是取模运算的乘法运算法则
(ab)mod m=[(amodm)(bmodm)] mod m

取模运算还有两个公式
公式①：$a^{b+1}$mod m=[a·($a^b$mod m)] mod m
所以由公式迭代可得$a^{b+1}$mod m=[a·($a^b$mod m)] mod m=[a·( a·($a^{b-1}$mod m)mod m )] mod m=……
解法一正是用了这个迭代公式

证明①：不妨令a=km+h,故
$a^{b+1}$mod m=[(a mod m)·($a^b$mod m)]mod m
=[h·($a^b$mod m)]mod m
=[(km+h)·($a^b$mod m)]mod m
=[a·($a^b$mod m)]mod m

公式②：$a^b$mod m=$(amodm{)}^b$mod m

证明②：不妨令a=km+h,故
$a^b$mod m=$(km+h{)}^b$mod m
=$h^b$mod m=$(amodm{)}^b$mod m

解法一运用公式①（时间复杂度比快速模运算算法高）

#include <iostream>
using namespace std;

int main()
{
    long long base,exponential;//分别代表底数与指数
    while(cin>>base&&cin>>exponential&&base!=0&&exponential!=0){
        int result=1;
        for(int i=0;i<exponential;i++){
            result=base*result%1000;//运用了公式①
        }
        cout<<result<<endl;
    }
    return 0;
}

解法一的递归形式也特别容易给出

#include <iostream>
using namespace std;

int fastMod(int a,int n)
{
    if(n==0){
        return 1;
    }
    else{
        return (a*(fastMod(a,n-1)))%1000;
    }
}

int main()
{
    int a,n;
    cin>>a>>n;
    cout<<fastMod(a,n);
    return 0;
}

解法二：快速模运算
其与下面的快速幂运算的代码十分类似

int fastPower(int a,int n)
{
    int base=a;
    int result=1;
    while(n){
        if(n&1){
            result*=base;
        }
        base*=base;
        n>>=1;
    }
    return result;
}

快速模运算的原理：将b用二进制的方法表示后重复使用公式(ab)mod m=[(amodm)(bmodm)] mod m对$a^b$mod m进行展开.

例$a^5$%m的快速模运算求解过程

此时result=={(a%m)* [($a^2$%m)*($a^2$%m) %m]} %m满足根据取模运算的乘法运算法则展开后得到的式子

如下是快速模运算此题代码

#include <iostream>
using namespace std;
int main() {
    long long base,exponential;
    //优化：此处为了防止base太大，可根据公式②先对base进行一次取模运算，即base=base%1000;
    while(cin>>base&&cin>>exponential&&base!=0&&exponential!=0) {
        int result=1;
        while(exponential) {
            if(exponential&1) {//指数为奇数时
                result=(result*base)%1000;
            }
            exponential>>=1;//相当于exponential/=2;
            base=(base*base)%1000;
        }
        cout<<result<<endl;
    }
    return 0;
}

解法三：快速模运算的递归形式
其也与下面的快速幂运算的递归形式代码十分类似

int fastPower(int a,int n)
{
    if(n==1){
        return a;
    }
    if(n&1){
        return a*fastPow(a*a,n/2);
    }
    else{
        return fastPow(a*a,n/2);
    }
}

#include <iostream>
using namespace std;

int fastMod(int a,int n)
{
    if(n==0){
        return 1;
    }
    if(n&1){
        return (((fastMod(a,n/2))*(fastMod(a,n/2)))%1000*(a%1000))%1000;
    }
    else{
        return ((fastMod(a,n/2))*(fastMod(a,n/2)))%1000;
    }
}

int main()
{
    int a,n;
    cin>>a>>n;
    cout<<fastMod(a,n);
    return 0;
}