Codeforces 900D (Codeforces Round #450 Div. 2) Unusual Sequences 容斥定理

57 阅读 0 评论 38 点赞

我是靠谱客的博主满意啤酒，最近开发中收集的这篇文章主要介绍Codeforces 900D (Codeforces Round #450 Div. 2) Unusual Sequences 容斥定理，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Count the number of distinct sequences a1, a2, ..., an (1 ≤ ai) consisting of positive integers such that gcd(a1, a2, ..., an) = x and $\text{[math]}$ . As this number could be large, print the answer modulo 109 + 7.

gcd here means the greatest common divisor.

Input

The only line contains two positive integers x and y (1 ≤ x, y ≤ 109).

Output

Print the number of such sequences modulo 109 + 7.

   Examples 
 
     input 
   
3 9

     output 
   
3

     input 
   
5 8

     output 
   
0

Note

There are three suitable sequences in the first test: (3, 3, 3), (3, 6), (6, 3).

There are no suitable sequences in the second test.

显然y必须是x的倍数，否则答案为0.

要想序列的gcd是x，则我们可以求出gcd是x的整数倍的序列个数，再利用容斥定理把它们减掉。

要求gcd为n*x的序列个数，我们可以把y分成k个n*x,再利用隔板法把它们隔开。这样，一共有2^(k-1)种序列。

若直接枚举n*x，个数太多。注意到n*x必须是y的因子，于是枚举y的因子缩小范围。

求出所有可能的因子之后，利用容斥定理从大到小推即可。

#include <cstdio>
#include <iostream>
#include <string.h>
#include <string> 
#include <map>
#include <queue>
#include <deque>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <stack>
#include <iomanip>
#define mem0(a) memset(a,0,sizeof(a))
#define meminf(a) memset(a,0x3f,sizeof(a))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
const int maxn=100005,inf=0x3f3f3f3f;  
const ll llinf=0x3f3f3f3f3f3f3f3f,mod=1e9+7;   
const ld pi=acos(-1.0L);
ll a[maxn],dp[maxn];

ll fastpower(ll base,ll index) {
	ll ans,now;
	if (index<0) return 1;
	ans=1;
	now=base;
	ll k=index;
	while (k) {
		if (k%2) ans=ans*now;
		ans%=mod;
		now=now*now;
		now%=mod;
		k/=2;
	}
	return ans;
}

int main() {
	ll x,y,i,j,n=0;
	cin >> x >> y;
	if (y%x!=0) {
		cout << 0;return 0;
	}
	for (i=1;i*i<=y;i++) {
		if (i%x==0&&y%i==0) a[++n]=i;
		if (i*i!=y&&y%(y/i)==0&&(y/i)%x==0) a[++n]=y/i;
	}
	sort(a+1,a+n+1);
	for (i=n;i>=1;i--) {
		dp[i]=fastpower(2,y/a[i]-1);
		for (j=i+1;j<=n;j++) {
			if (a[j]%a[i]==0) dp[i]-=dp[j];
			dp[i]=(dp[i]+mod)%mod;
		}
	}
	cout << dp[1];
	return 0;
}