一.快速幂模板

int Powermod(int a,int b,int MOD){       int t=1;       while (b>0)       {              if (b%2==1)                t=(t*a)%MOD;              b/=2;              a=(a*a)%MOD;       }       return t;}//(a^b)%MOD

 参考：

二.取模运算的性质：

（1）（a+b)%c=(a%c+b%c)%c

（2）（ab)%c=(a%c)(b%c)%c

三.相关题目

Noip2013TG D1T1转圈游戏

不难得出 ans=(x+m*10^k)%n

由数据范围，使用快速幂来做

1 #include
         
           2 #include
          
            3  4 long long Powermod(int a,int b,int c) 5 { 6     int t=1; 7     while(b>0) 8     { 9         if (b%2==1)10          t=(t*a)%c;11         b/=2;12         a=(a*a)%c;13     }14     return t;15 }16 17 int main()18 {19   long long x,m,k,n;20   scanf("%lld%lld%lld%lld",&n,&m,&k,&x);21   printf("%d",(x+m*Powermod(10,k,n))%n);22   return 0;23 }
          
         

 

Bzoj1008越狱

首先我认为题目的表述有些值得商榷的地方，“每个犯人可能信仰其中一种”，是否包含不信仰宗教的情况？ 正确答案中是按照每个人都信仰一种宗教来做的。

一共会有m^n种情况。由于直接求会发生越狱的情况数较麻烦，故可以先算不会越狱的情况：第一间有m种选择，第二间则有(m-1)种选择（不与第一间相同），以此类推，根据乘法原理，共有m*(m-1)^(n-1)种情况

则ans=m^n-m*(m-1)^(n-1)

由于1<=M<=10^8,1<=N<=10^12，所以需要使用快速幂

1 #include
         
           2  3 const int MOD=100003; 4 long long m,n,tmp,cnt; 5  6 int Powermod(long long a,long long b,long long c){ 7     int i=1; 8     while(b>0) 9     {10         if (b%2==1)11           i=(i*a)%c;12         b/=2;13         a=(a*a)%c;14     }15     return i;16 }17 18 int main()19 {20     scanf("%lld%lld",&m,&n);21     tmp=Powermod(m,n,MOD);22     cnt=Powermod(m-1,n-1,MOD);23     cnt=(cnt*m)%MOD;24     long long ans=(tmp-cnt+MOD)%MOD;25     printf("%lld",ans);26     return 0;27 }