hdu 4704 Sum （整数和分解+快速幂+费马小定理降幂）

题意：

给n（1<n<）,求(s1+s2+s3+...+sn)mod(1e9+7)。其中si表示n由i个数相加而成的种数,如n=4,则s1=1,s2=3。（全题文末）

知识点：

整数n有种和分解方法。

费马小定理：p是质数，若p不能整除a，则 a^(p-1) ≡1（mod p）。可利用费马小定理降素数幂。

当m为素数，（m必须是素数才能用费马小定理）

a=2时。（a=2只是题中条件，a可以为其他值）

mod m = * // k=

= //==1为费马小定理的应用

例如，设p=7, n=32, 求2^32≡x(mod p)的值

由于p是素数，所以一定存在2^6≡1(mod p)

则

2^32%p=(2^[(6*5)+2])%p

=[2^(6*5)*2^2]%p

=[(2^(6*5)%p)*(2^2%p)]%p //(a*b)%m=[(a%m)*(b%m)]%m;

=[1*(2^2%p)]%p //2^(6*5)%p为对费马小定理的应用

=2^2%p;

题解：

题目相当于求n的分解种数。例如,n=x1+x2+x3+..xk是一种分解，把xi看成由xi个1组成，同理n即为n个1组成。

题目也就是给n个1分组的方法数（这不是类似于组合数学的小球间隔板问题吗）。每两个1之间是否放隔板，有放和不放两种选择，一共n-1个可选择间隔。so 总方法数为。

由于n太大，不好处理啊。

指数太大，发现m=1e9+7为素数，则可用费马小定理(a^(p-1))≡1(mod p))降幂。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

typedef long long LL;

const int mod=1e9+7,N=1e5+5;

char a[N];

LL quick_mod(LL a,LL p)          //快速幂 (快速幂利用了二分思想和秦九昭算法)

{

    LL ans=1;

    while(p)

    {

        if(p&1)

            ans=ans*a%mod;

        a=a*a%mod;

        p>>=1;

    }

    return ans;

}

int main()

{

    while(~scanf("%s",a))

    {

        int len=strlen(a);

        LL ans=0;

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

        {

            ans=(ans*10+a[i]-'0')%(mod-1);

        }

        ans=(ans-1+mod-1)%(mod-1);

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

    }

    return 0;

}

这道题还可以找循环结。

发现 2^500000003 = 1 = 2^0，所以n=(n-1)%500000003，所以 2^(n - 1) = 2^((n-1)%(mod -1))%mod; （mod-1=500000003）

Sum

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

Submit Status

Description

Sample Input

Sample Output

Hint

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

巴特西

hdu 4704 Sum （整数和分解+快速幂+费马小定理降幂）

最新文章

热门文章