【CF900D】Unusual Sequences

题意：定义正整数序列$a_1,a_2...a_n$是合法的，当且仅当$gcd(a_1,a_2...a_n)=x$且$a_1+a_2+...+a_n=y$。给定x,y，求合法的序列总数。

x,y<=10^9。

题解：不难想到容斥，先不管gcd的限制，那么总方案数就是$2^{y-1}$。你可以理解为有y个1，除了第一个1，其余的要么加到上一个数中去，要么自己变成一个新数。

如果考虑gcd的限制呢？容斥一发即可。并且容斥系数就是我们常用的莫比乌斯函数。

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

typedef long long ll;

const ll P=1000000007;

int n,m,tot;

ll ans;

int p[10];

inline ll pm(ll x,ll y)

{

	ll z=1;

	while(y)

	{

		if(y&1)	z=z*x%P;

		x=x*x%P,y>>=1;

	}

	return z;

}

void dfs(int x,int y,int z)

{

	if(x>tot)

	{

		ans=(ans+P+pm(2,n/y-1)*z%P)%P;

		return ;

	}

	dfs(x+1,y,z),dfs(x+1,y*p[x],-z);

}

int main()

{

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

	if(n%m)

	{

		puts("0");

		return 0;

	}

	n/=m;

	int i,t=n;

	for(i=2;i*i<=t;i++)	if(t%i==0)

	{

		p[++tot]=i;

		while(t%i==0)	t/=i;

	}

	if(t!=1)	p[++tot]=t;

	dfs(1,1,1);

	printf("%I64d",ans);

	return 0;

}

巴特西

【CF900D】Unusual Sequences 容斥（莫比乌斯反演）

【CF900D】Unusual Sequences

最新文章

热门文章