欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU - 4704(费马小定理和快速幂)

程序员文章站 2022-06-08 11:19:26
...
HDU - 4704(费马小定理和快速幂)

Input
2
Output
2

        
 
Hint
1. For N = 2, S(1) = S(2) = 1.2. The input file consists of multiple test cases.
Sample Input
2
Sample Output
2


代码 :

其实我看不懂是题目是搜索博客的这道题就是x1+x2+x3+···+xn=N,求有几种组合方法。

利用数学方法中的“隔板法”,不难知道结果就是C(n-1)^0+C(n-1)^1+C(n-1)^2+···+C(n-1)^r+···+C(n-1)^(n-1).这是二项式定理的展开式。 根据二项式定理不难得出,结果就是2^(n-1)。所以,这道题就转换为求解2^(n-1)mod(1e9+7)


#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
char str[100005];
const LL mod=1e9+7;
//快速幂 
LL FastPow(LL a,LL b)
{
	LL ans=1;  
	while(b)  
	{  
	    if(b&1)  
	    	ans=ans*a%mod;  
	    a=a*a%mod;  
	    b>>=1;  
	}  
	   return ans;  
}
//费马小定理 
LL FeiMaXiao(char *str)
{
	LL ans=0;
	for(int i=0;str[i]!='\0';i++)
		ans=(ans*10+str[i]-'0')%(mod-1);
	return ans;
}
int main()
{
	while(scanf("%s",str)!=EOF)
	{
		LL n = FeiMaXiao(str);
		printf("%lld\n",FastPow(2,n-1));
	}
    return 0;
}