HDU6363

まず、いくつかの結論gcd(2^a-1,2^b-1)=2^(gcd(a,b))-1を知る必要があります.gcd(F[cnt 1],F[cnt 2])=F[gcd(cnt 1,cnt 2)]も知らなければならない.この2つの結論は数学的帰納法で導くことができ、2番目はF配列の隣接する2つの要素の相互質を知ることができ、この問題は1つのgcdにとって、彼の貢献は2^(F(gcd))−1ほどである.一方、nをk部に分けてgcdをgcdの倍数とするには、n本書と同様にk個の本棚が異なり、シナリオ数はc(n/gcd+k-1,k-1)であり、セパレータ法を用いる思想であり、gcdが現在列挙されているgcdであることが要求される場合、モビウス関数を用いて反発し、gcdの倍数-gcdの2倍のシナリオ数、-gcdの3倍のシナリオ数+がgcdの4倍のシナリオ数である.ansはすべてのgcdを列挙し、その後モビウスが反転して得た各gcdのスキーム数と、最後の総スキーム書はc(n+k−1,k−1)であり、彼の逆元を乗じるとよい.総複雑度はT*n*lnnであるが,実際には143 msしか走っておらず,int演算を用いるのは非常に速い.

#include
#include
#define maxl 2000010
#define mod 1000000007

int n,k;
int mu[maxl],p[maxl],F[maxl];
int jc[maxl],jcinv[maxl];
bool no[maxl];
int ans;

inline void shai()
{
	int t,j;
	mu[1]=1;no[1]=true;
	for(int i=2;i>=1;
	}
	return ans;
}

inline int c(int n,int r)
{
	if(n<0 || r<0 || r>n) return 0;
	if(r==0 || n==r) return 1;
	return (1ll*((1ll*jc[n]*jcinv[n-r])%mod)*jcinv[r]%mod)%mod;
}

inline void init()
{
	shai();
	jc[0]=1;
	for(int i=1;i=1;i--)
		jcinv[i]=(1ll*jcinv[i+1]*(i+1))%mod;
	F[0]=0;F[1]=1;
	for(int i=2;i