引入

在求解式子a^b mod k时，我们通常使用循环语句进行求解。但当b的值很大，例如达到了10⁹时，该式子的求解时间消耗就非常大了。因此，我们需要思考另外的方法，使得快速求幂成为可能。

引理

陈述

对于x=p·q(x,p,q∈Z₊)，有x mod k=(p mod k)(q mod k)mod k。

证明

设p=a·k+c，q=b·k+d，

则x=(a·k+c)(b·k+d)=a·b·k²+a·d·k+b·c·k+c·d，

∴x mod k=c·d mod k，

又∵(p mod k)(q mod k)mod k=c·d mod k，

∴x mod k=(p mod k)(q mod k)mod k。

方法

根据以上引理，我们知道，对于a^b mod k，可以将b进行二进制拆分。例如对于b=6，其二进制表示为110，那么a⁶ mod k=(a⁴ mod k)·(a² mod k)mod k。

于是，我们只需要将a不断平方，b不断右移，如果b二进制表示末位为1，就在最后结果中累乘入当前的a，就可以得到最终结果。

这样，我们可以将求幂运算进行优化，使它的时间复杂度降低至O(log n)。

1 long long quick_power(long long a,long long b,long long mod) 2 { 3     long long result=1,t=a; 4     while(b) 5     { 6         if(b&1) 7             result=result*t%mod; 8         t=t*t%mod; 9         b>>=1;10     }11     return result%mod;12 }

例题

·/

·题目描述

监狱有连续编号为1到n的n个房间，每个房间关押一个犯人。有m种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人信仰的宗教相同，就可能发生越狱。求有多少种状态可能发生越狱。（结果对100003取余）

·题目分析

求有多少种状态可能发生越狱，听起来是一个很难的问题。我们不妨换一种角度思考，求出有多少种状态不会发生越狱，再用总状态数减去这个数目，就得到了可能发生越狱的状态数。

由于有m种宗教，n个房间，根据乘法原理，总状态数为mⁿ。而求有多少种状态不会发生越狱，对于第一个人，可以任意信仰哪一种宗教，而对于之后的每一个人，只需要保证与前面的人信仰的宗教不相同即可，状态数为m·(m-1)^n-1。我们要求的答案即为(mⁿ-m·(m-1)^n-1)mod 100003。

这里有一点需要注意。取余运算中，mⁿ mod 100003的结果可能小于m·(m-1)^n-1 mod 100003，减法操作可能出现负数，再次取余将会变成负数而非我们想要的正数。因此，我们应该在进行减法操作之前加上100003，避免负数的出现。

·代码

1 #include
      
        2 using namespace std; 3 long long m,n; 4 const int MOD=100003; 5 long long quick_power(long long a,long long b,long long k) 6 { 7     long long result=1,t=a; 8     while(b) 9     {10         if(b&1)11             result=result*t%k;12         t=t*t%k;13         b>>=1;14     }15     return result%k;16 }17 int main()18 {19     scanf("%lld%lld",&m,&n);20     printf("%lld",(quick_power(m,n,MOD)+MOD-quick_power(m-1,n-1,MOD)*m%MOD)%MOD);21     return 0;22 }