乘方快速幂 OR 乘法快速幂

关于快速幂这个算法，已经不想多说，很早也就会了这个算法，但是原来一直靠着模板云里雾里的，最近重新学习，发现忽视了一个重要的问题，就是若取模的数大于int型，即若为__int64的时候应该怎么办，这样就得用到乘法快速幂+乘方快速幂了。

快速幂一般是为了解决乘方取模问题的，显然思想就是二分，下面贴上快速幂模板：

 __int64 mulpow(__int64 a,__int64 p,__int64 m)
 {
     __int64 ans = ;
     while(p)
     {
         if(p&)
             ans = ans * a % m;
         p >>= ;
         a = a * a % m;
     }
     return ans;
 }

但是以上代码有个问题，并不适合m超过int的情况，下面提供m超过int情况的解法

 __int64 multi(__int64 a,__int64 b,__int64 n)  //乘法快速幂
 {
     __int64 temp=;
     while(b)
     {
         if(b&)
         {
             temp+=a;
             if(temp>=n)  temp-=n;
         }
         a<<=;
         if(a>=n) a-=n;
         b>>=;
     }
     return temp;
 }

 __int64 mulpow(__int64 a,__int64 m,__int64 n)  //乘方快速幂
 {
     __int64 temp=;
     a%=n;
     while(m)
     {
         if(m&)  temp=multi(temp,a,n);
         a=multi(a,a,n);
         m>>=;
     }
     return temp;
 }

但缺点就是速度慢了点，logn*logn的，感谢南理工的《ACM算法训练教程》

poj3761

链接：http://poj.org/problem?id=3761

排列组合题目，但是真不好想，看了别人的题解才做出来的，orz别人的思维，是自己太弱了

题解：http://blog.****.net/cscj2010/article/details/7820906

这题典型的用快速乘方幂+快速乘法幂会TLE的

 #include<iostream>
 #include<cstdio>
 #include<cstring>
 #include<string>
 #include<cmath>
 #include<vector>
 #include<algorithm>
 using namespace std;
 const int maxn=;
 __int64 a[maxn];
 const int mod=;
 __int64 mulpow(__int64 a,__int64 n,__int64 m)
 {
     __int64 temp=;
     while(n)
     {
         if(n&) temp=temp*a%m;
         a=a*a%m;
         n>>=;
     }
     return temp;
 }
 int main()
 {
     __int64 n,k,T;
     a[]=;
     for(int i=;i<=maxn;i++)
        a[i]=a[i-]*i%mod;
     scanf("%I64d",&T);
     while(T--)
     {
         scanf("%I64d%I64d",&n,&k);
         printf("%I64d\n",(a[k]*((mulpow(k+,n-k,mod))-mulpow(k,n-k,mod)+mod)%mod)%mod);
     }
     return ;
 }