HDU4704:Sum（欧拉降幂公式）

Input

Output

Sample Input

由公式，ans=2^(N-1)%Mod=2^((N-1)%(Mod-1)+(Mod-1)) %Mod。

注意：降幂的之后再加一个Mod-1保险，避免为负，比如此题出入1000000006时，就出问题了。

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define ll long long

const int Mod=1e9+;

char c[];

ll ans,sum,g;

ll qpow(ll a,ll x){

    ll res=;

    while(x){

        if(x&) res=res*a%Mod;

        x>>=;

        a=a*a%Mod;

    }

    return res;

}

int main()

{

    int L,i,j;

    while(~scanf("%s",c+)){

        L=strlen(c+);

        sum=;g=;

        for(i=L;i>=;i--){

            sum=(sum+(c[i]-'')*g)%(Mod-);

            g=g*%(Mod-);

        }

        ans=qpow(,sum+Mod-);

        printf("%lld\n",ans);

    }

    return ;

}

巴特西

HDU4704:Sum（欧拉降幂公式）

最新文章

热门文章