BZOJ 1008 快速幂

暴力递推，转化成通项公式，利用补集法求解~

注意负数情况。。。

好久不写快速幂了，竟然没写错~

View Code

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <algorithm>
 5 #include <cstdlib>
 6 
 7 #define mod 100003
 8 
 9 using namespace std;
10 
11 long long n,m;
12 
13 inline long long pow(long long a,long long b)
14 {
15     long long res=1;
16     while(b)
17     {
18         if(b&1) res=(res*a)%mod;
19         a=(a*a)%mod;
20         b>>=1LL;
21     }
22     return res;
23 }
24 
25 inline void go()
26 {
27     cin>>m>>n;
28     long long a=pow(m,n);
29     long long b=(pow(m-1,n-1)*(m%mod))%mod;
30     a+=mod;
31     cout<<(a-b)%mod<<endl;
32 }
33 
34 int main()
35 {
36     go();
37     return 0;
38 }