记录编号	126674	评测结果	AAAAAAAAAA
题目名称	[SPOJ 2734] 盛大的派对	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.176 s
提交时间	2014-10-13 22:01:00	内存使用	0.34 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int SIZE=1010;
LL MOD=100000007;
int N,K;//不能有超过K个连续的女生
LL f[SIZE]={0};//长度为i且最后一个是男生的方案
LL fs[SIZE]={0};//f的前缀和
LL g[SIZE]={0};//长度为i
LL realmod(LL x){
	x%=MOD;
	if(x<0) x+=MOD;
	return x;
}
LL calc_ring(int n){//长度为n的环
	LL ans=0;
	if(K>=N) ans=1;//这是没有1的
	for(LL i=0;i<=K&&i<n;i++)//枚举:最后一个1到首个1,中间有i个0
		ans=realmod(ans+f[n-i-1]*(i+1));
	return ans;
}
int phi(int x){
	int ans=x;
	for(int i=2;i*i<=x;i++){
		if(x%i==0){
			ans=(ans/i)*(i-1);
			while(x%i==0) x/=i;
		}
	}
	if(x>1) ans=(ans/x)*(x-1);
	return ans;
}
LL quickpow(LL a,LL n){
	LL ans=1;
	while(n){
		if(n&1) ans=(ans*a)%MOD;
		a=(a*a)%MOD;
		n>>=1;
	}
	return ans;
}
LL calc(int l,int p){
	return realmod(calc_ring(l)*phi(p));
}
void work(void){
	LL ans=0;
	for(int i=1;i*i<=N;i++){
		if(N%i==0){
			ans+=calc(i,N/i);
			if(i*i<N){
				ans+=calc(N/i,i);
			}
		}
	}
	ans=realmod(ans*quickpow(N,MOD-2));
	printf("%lld\n",ans);
}
void prepare_f(void){
	f[0]=fs[0]=1;
	for(int i=1;i<=N;i++){
		f[i]=fs[i-1];
		if(i-K-2>=0) f[i]-=fs[i-K-2];
		f[i]=realmod(f[i]);
		fs[i]=realmod(fs[i-1]+f[i]);
	}
}
int main(){
	freopen("largeparty.in","r",stdin);
	freopen("largeparty.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&N,&K);
		prepare_f();
		work();
	}
	return 0;
}