hdu 4704 sum（费马小定理+快速幂）

题意：

这题意看了很久。。

s（k）表示的是把n分成k个正整数的和，有多少种分法。

例如：

n=4时，

s（1）=1 4

s（2）=3 1，3 3，1 2，2

s（3）=3 1，1，2 1，2，1 2，1，1

s（4）=1 1，1，1，1

s（1）+s（2）+s（3）+s（4）=1+3+3+1=8

当n=1，2，3，4时，可以分别求出结果为 1，2，4，8

于是推出答案就是2^(n-1)---------------------（为什么？我也不知道，这个是怎么推出来的）

思路：题意明白了，就是求2^(n-1) mod（10^9+7）呗。

由于这里的n非常大，1<=n<10^100000，这里用简单的暴力绝对超时啊（10^8就会超时）

那么，这里用了两个优化，一个是费马小定理 a^(p-1)≡1(mod p)，另外就是快速幂加速求幂

这里稍微演示一下如何利用费马小定理处理：

（单单用费马小定理处理仍会超时，因为处理完后，指数最大能达到10^9级别，仍会超时）

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int mod=1e9+7;

void pow(__int64 b){//快速求幂（位操作）

	__int64 a=2;

	__int64 ans;

	ans=1;

	while(b>0){

		if(b&1)//判断是否为奇数，相当于 if(b%2==1)

			ans=(ans*a)%mod;

		a=(a*a)%mod;

		b=b>>1;//二进制向右移一位，相当于 b=b/2;

	}

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

}

int main(){

	char str[123456];

	__int64 num,i;

	while(~scanf("%s",str)){

		num=0;

		int len=strlen(str);

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

			num=( num*10+(str[i]-'0') )% (mod-1);//精华部分

		}

		if(num==0) pow(mod-2);//此时n=mod-1,所以应该求pow(mod-2),而不能求成pow(num-1)

		else pow(num-1);

	}

	return 0;

}

巴特西

hdu 4704 sum（费马小定理+快速幂）

最新文章

热门文章