CRB and Candies（数论综合题：求有关自然数与组合数的最小公倍数性质关系+快速幂求逆元）

最新推荐文章于 2019-08-26 19:46:00 发布

林下的码路

最新推荐文章于 2019-08-26 19:46:00 发布

阅读量896

点赞数

分类专栏：数论 HDU ACM 文章标签： ACM 算法

本文链接：https://blog.csdn.net/Enjoying_Science/article/details/48086005

版权

ACM 同时被 3 个专栏收录

521 篇文章

订阅专栏

HDU

171 篇文章

订阅专栏

数论

79 篇文章

订阅专栏

Link：http://acm.hdu.edu.cn/showproblem.php?pid=5407

CRB and Candies

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 632 Accepted Submission(s): 312

Problem Description

CRB has

N different candies. He is going to eat

K candies.
He wonders how many combinations he can select.
Can you answer his question for all

K (0 ≤

K ≤

N )?
CRB is too hungry to check all of your answers one by one, so he only asks least common multiple(LCM) of all answers.

Input

There are multiple test cases. The first line of input contains an integer

T , indicating the number of test cases. For each test case there is one line containing a single integer

N .
1 ≤

T ≤ 300
1 ≤

N ≤

106

Output

For each test case, output a single integer – LCM modulo 1000000007(

109+7 ).

Sample Input

Sample Output

Author

KUT（DPRK）

Source

2015 Multi-University Training Contest 10

编程思想：证明不会，直接上结论

g(N) = LCM(C(N,0),C(N,1),...,C(N,N))

$f(n)\ =\ LCM(1, 2, ..., n)$ , the fact $g(n)\ =\ f(n+1) / (n+1)$

$f(n)\ =\ LCM(1, 2, ..., n)$ $f (1) = 1$

If $n\ =p^{k}$ then $f(n)\ =\ f(n-1) \times \ p$ , else $f(n)\ =\ f(n-1)$ .

附上证明链接：

http://www.zhihu.com/question/34859879/answer/60168919

http://arxiv.org/pdf/0906.2295v2.pdf

AC code：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define LL long long
#define MAXN 1000010
using namespace std;
const int INF=0xffffff;
const int mod=1e9+7; 
LL a[MAXN],b[MAXN];//b(n)=LCM[C(n,0),C(n,1),...,C(n,n)],a(n)=LCM[1,2,3,...,n]
LL p[MAXN];//p[i]纪录i的最大质因子 
LL ans;
bool judge(int x)//判断x是否是其最大质因子p[x]的k次幂，即是否有x=p^k，其中p是x的最大质因子，k为正整数 
{
	int d=p[x];
	while(x%d==0&&x>1)
	{
		x/=d;
	}
	return x==1;//返回true说明x是其最大质因子的k次幂，返回false说明不是 
}
void get_maxprime()//筛法求i的最大质因子
{
	for(int i=1;i<MAXN;i++) p[i]=i; 
	for(int i=2;i<MAXN;i++)
		if(p[i]==i)
			for(int j=i+i;j<MAXN;j+=i) p[j]=i;
}
void getlcm1()//求a(n)=LCM[1,2,3,...,n]%mod
{//对于a(n)，我们有：当p是素数且n=p^k时,a(n)=p*b(n-1),否则a(n)=a(n-1)
	get_maxprime();//筛法求i的最大质因子
	a[0]=1;
	for(int i=1;i<MAXN;i++)
	{
		if(judge(i)) a[i]=a[i-1]*p[i]%mod;
		else a[i]=a[i-1];
	} 
} 
LL pow_m(LL a,LL n)//快速模幂运算,求(a^n)%MOD  
{
    LL res=1;
    LL tmp=a%mod;
    while(n)
    {
        if(n&1){res*=tmp;res%=mod;}
        n>>=1;
        tmp*=tmp;
        tmp%=mod;
    }
    return res;
}
LL  inv(LL x,LL mod)//利用快速幂求x的逆元
{
	return  pow_m(x,mod-2); 
}
LL getlcm2(LL n)//求b(n)=LCM[C(n,0),C(n,1),...,C(n,n)]%mod
{//b(n)=a(n+1)/(n+1)
	LL res=a[n+1]*inv(n+1,mod)%mod;
	return res;
}  
int main()
{
	getlcm1();//求a(n)=LCM[1,2,3,...,n]%mod
	int t,n;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		ans=getlcm2(n);//求b(n)=LCM[C(n,0),C(n,1),...,C(n,n)]%mod
		printf("%I64d\n",ans); 
	}
	return 0;
}