D. Unusual Sequences(排列计数+容斥)

57 阅读 0 评论 38 点赞

我是靠谱客的博主发嗲大叔，最近开发中收集的这篇文章主要介绍D. Unusual Sequences(排列计数+容斥)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目

题意：

给定x和y，求出满足下列条件的序列个数。1:序列的gcd为x,2:序列的和为y。
$1 ≤ x, y ≤ 10^9$

分析：

显然这些数字必须是x的倍数，所以y必然也是x的倍数，现在就是有y/x个x让我们操作。我们直接除以x，要求的就变成gcd为1了。现在有y/x个x，那么形成的数列种数有多少呢，用不定方程的正整数解，变量个数从1~y/x，就可以得出2^(y/x-1)。
但是并不是这些序列的gcd一定为1，所以我们需要减去gcd为别的。那么gcd还可能有什么呢，显然是y/x的因子。所以ma[x]表示和为x且gcd为1的序列种数，那么其中gcd为z的就可以表示为ma[x/z] (每z个为一组)。所以ma[x] = 2^(x-1)-ma[t] (t为x的因子)。

#include <iostream>
#include <vector>
#include <map>
using namespace std;

typedef long long ll; 
ll mod = 1e9 + 7;
map<ll,ll> ma;

ll q_pow(ll a,ll b)
{
	ll res = 1;
	while( b )
	{
		if( b & 1 )
		{
			res *= a;
			res %= mod;
		}
		a *= a;
		a %= mod;
		b >>= 1;
	}
	return res;
}

int slove(int n)
{
	if( ma[n] ) return ma[n];
	if( n == 1 ) return ma[n] = 1;
	ma[n] = q_pow(2,n-1);
	for (int i = 2; i * i <= n; i++)
	{
		if( n % i == 0 )
		{
			ma[n] = ( ma[n] - slove(n/i) + mod ) % mod;
			if( i * i != n ) ma[n] = (ma[n] - slove(i) + mod) % mod; 
		}
	}
	ma[n] = ( ma[n] - slove(1) + mod ) % mod;
	return ma[n];
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll x,y;
	cin >> x >> y;
	if( y % x != 0 )
	{
		cout << 0 << 'n';
		return 0;
	}
	cout << slove(y/x) << 'n';
	return 0;
}