SUM 大数取余 欧拉定理 二项展开 数论

SumTime Limit:1000MS????Memory Limit:131072KB????64bit IO Format:%I64d & %I64u

Submit
Status

Description

?

Sample Input

    
    
     
     2 
    
    

?

Sample Output

    
    
     
     2 
    
    

Hint

 1. For N = 2,S(1) = S(2) = 1. 2. The input file consists of multiple test cases. 

??? 核心就是求一个组合的问题，对于一个固定的k，意思是有k个大于1的数字之和为N，那么我们可以将N表示为N个1，然后我们在这些1之间插入隔板，插入m个隔板，我们将得到m+1个组，因此如我我们要得到k组，我们只需要插入k-1个隔板，一共有N-1个空，因此共有C（n-1，k-1）种组合，于是，题目实际上要求C（n-1,0）+C（n-1,1）+…+C（n-1，n-1）=2^(n-1)。

??? 于是，问题就被转化为求一个指数幂取余，我们很明显知道要用快速幂，但是数据范围太大，仔细观察，可以发现MOD=10^9+7是一个与2互质的数，这样的话就可以利用欧拉定理，

但是欧拉定理的指数是欧拉函数，不过我们又知道，质数的欧拉函数是其值减一，而

a^n==a^(k*oula(p)+r)==a^(k*oula(p))*a^r (mod m),其中a^(k*oula(p))部分为1，这个可以由欧拉定理得到，于是问题进一步简化为求a^r，其中r=n%（oula（p）），这时候，oula（p）=p-1，其范围仍然较大，因此可以使用大数取余法，然后再使用快速幂。

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
typedef long long ll;
const ll MOD=1000000007;

ll PowerMod(ll a,ll b,ll c)
{
    ll ans = 1;
    a = a % c;
    while(b>0)
    {
        if(b % 2 == 1)
            ans = (ans * a) % c;
        b = b/2;
        a = (a * a) % c;
    }
    return (ans+c)%c;
}


ll Mod(char a[],int len,ll b)
{
    ll ans=0;
    for(int i=0;i<len;i++)
    {
        ans=(ans*10%b+(a[i]-'0'))%b;
    }
    return ans;
}

int main()
{
    char N[100010];
    ll ans,p,len,mod;
    //N[0]=N[1]=1;
    //cout<<Mod(N,2,3);
    mod=MOD-1;
    while(~scanf("%s",N))
    {
        len=strlen(N);
        p=Mod(N,mod);
        p=(p-1+mod)%mod;
        ans=PowerMod(2,MOD);
        printf("%lld\n",ans);
        //printf("%I64d\n",ans);
    }

    return 0;
}