hdu 4704 Sum【组合数学/费马小定理/大数取模】By cellur925

首先，我们珂以抽象出S函数的模型：把n拆成k个正整数，有多少种方案？

答案是C(n-1,k-1)。

然后发现我们要求的是一段连续的函数值，仔细思考，并根据组合数的性质，我们珂以发现实际上答案就是在让求2^(n-1)。

然鹅我们并不能高兴地过早。因为n的数量级竟然到了丧心病狂的1e100000.连高精度都救不了它。

费马小定理

费马小定理有两种形式： $a^{p-1}$≡1($mod$ $p$) 与 $a^p$≡$a$($mod$ $p$)。第二种形式更为通用，是因为第一种形式不能涵盖“$a$是$p$的倍数”的情况，不够完善。第二种更加严谨。

*　　Update：其实这是扩展欧拉定理。思考了一上午后来被大佬告知这是一个定理...

定理可戳这位大佬的文章。

那么对于本题。我们就求$2^{{n-1}%{p-1}}%p$就行了...还要大数取膜...恶心。

$Code$

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 typedef long long ll;

 const ll moder=1e9+;

 char seq[];

 ll ksm(ll a,ll b)

 {

     ll ans=;

     while(b)

     {

         if(b&) ans=ans*a%moder;

         b>>=;

         a=a*a%moder;

     }

     return ans;

 }

 int main()

 {

     while(scanf("%s",seq+)!=EOF)

     {

         ll m=moder-;

         ll tmp=;

         int len=strlen(seq+);

         for(int i=;i<=len;i++)

         {

             tmp=tmp*+seq[i]-'';

             if(tmp>=m) tmp=tmp%m;

         }

         tmp=(tmp-+m)%m;

         printf("%lld\n",ksm(,tmp));

     }

     return ;

 }

巴特西

hdu 4704 Sum【组合数学/费马小定理/大数取模】By cellur925

最新文章

热门文章