hdu 5187高速べき乗

タイトル:http://acm.hdu.edu.cn/showproblem.php?pid=5187 あなたにn個の数をあげて、それからこのn個の数を並べて、規則は先に上がってから下がるか、先に下がってから上がるかです.分析:実は法則はとても簡単で、極値を確定すれば、順序は一定です.しかし、n,pの範囲に注意してください.例えばn=1,p=1の場合である.全部でn個の位置があり、位置ごとに2種類選択され、合計2^nのうち、頭と尾がそれぞれ繰り返される1つを減算します.n,pの範囲は(1≦n,p≦1018)なので,直接乗算するとオーバーフローするので,バイナリ乗算に分解する

#include<cstdio>
#include<cstring>
typedef long long ll;
ll mul(ll a,ll b,ll c) //a*b   ，   b      ，    
{
    ll res=0;
    for(;b;b>>=1){
        if(b&1){
            res+=a;
            while(res>=c)res-=c;
        }
        a<<=1;
        while(a>=c)a-=c;
    }
    return res;
}
ll qmod(ll a,ll n,ll p)
{
    ll ans=1;
    for(;n;n>>=1){
        if(n&1)ans=mul(ans,a,p);
        a=mul(a,a,p);
    }
    return ans;
}
int main()
{
    ll n,p;
    while(~scanf("%I64d%I64d",&n,&p)){
        if(n==1)printf("%d
",n%p);
        else
        printf("%I64d
",(qmod(2ll,n,p)-2+p)%p);
    }
    return 0;
}