【CF900D】Unusual Sequences

题目

智力下降严重

显然要反演了呀

首先必须满足\(x|y\)，否则答案是\(0\)

我们枚举这个数列的\(gcd\)是\(d\)或者\(d\)的倍数

于是答案就是

\[\sum_{x|d}[d|y]\mu(\frac{x}{d})g(\frac{y}{d})
\]

\(g(d)\)表示和为\(d\)的正整数数列的数量，显然就是插一下板，于是\(g(d)=\sum_{i=1}^d\binom{d-1}{i-1}=2^{d-1}\)

代码

#include<bits/stdc++.h>

#define re register

#define LL long long

inline int read() {

	char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;

}

const int mod=1e9+7;

const int maxn=1e5+5;

inline int ksm(int a,int b) {

	int S=1;

	for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) S=1ll*S*a%mod;

	return S;

}

int n,m,T,ans;

int f[maxn],p[maxn>>1],mu[maxn];

inline int getmu(int x) {

	if(x<=T) return mu[x];int now=0;

	for(re int i=1;i<=p[0]&&x!=1;++i) {

		if(x%p[i]) continue;

		x/=p[i];now^=1;

		if(x%p[i]==0) return 0;

	}

	if(x!=1) now^=1;

	if(!now) return 1;return -1;

}

inline void add(int i) {

	if(i%n) return;

	int x=getmu(i/n);

	if(x==1) ans=(ans+ksm(2,m/i-1))%mod;

	if(x==-1) ans=(ans-ksm(2,m/i-1)+mod)%mod;

}

int main() {

	scanf("%d%d",&n,&m);

	if(m%n) {puts("0");return 0;}

	T=std::ceil(std::sqrt(m/n));f[1]=mu[1]=1;

	for(re int i=2;i<=T;i++) {

		if(!f[i]) p[++p[0]]=i,mu[i]=-1;

		for(re int j=1;j<=p[0]&&p[j]*i<=T;++j) {

			f[p[j]*i]=1;if(i%p[j]==0) break;

			mu[p[j]*i]=-1*mu[i];

		}

	}

	for(re int i=1;i*i<=m;++i) {

		if(m%i) continue;

		add(i);if(m/i!=i) add(m/i);

	}

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

	return 0;

}

巴特西

【CF900D】Unusual Sequences

最新文章

热门文章