本文共 1176 字，大约阅读时间需要 3 分钟。

题意：

正整数序列  ，序列的  是  ，并且序列之和是  。

问这样的序列个数，答案取模。

数据范围： 。

题解：

容易发现存在这样的序列等价于  。

简化一下题意，这样的序列是  是  ，并且序列之和是  。

 是  ，并且序列之和是  的函数  是不好求的。

序列之和是  的函数  是很好求的。 

这样就考虑莫比乌斯反演了。

想一想会发现，  。

反演一下， 。

通过插板法可以知道  。

感受：

容斥题，可以考虑莫比乌斯反演。

代码：

#include
   
    using namespace std ;typedef long long ll ;const ll mod = 1e9 + 7 ;ll qpow(ll a , ll b){   ll ans = 1 ;    a %= mod ;   while(b)   {     if(b & 1)  ans = (ans * a) % mod ;     b >>= 1 , a = (a * a) % mod ;   }   return ans % mod ;}ll get_mu(ll n){    ll x = n , temp = n ;    ll cnt = 0 , now = 0 ;    for(ll i = 2 ; i * i <= x ; i ++)	{        now = 0 ;        if(x % i == 0)		{            while(x % i == 0)  now ++ , x /= i ;            if(now > 1) return 0 ;            cnt ++ ;        }    }    if(x != 1) cnt ++ ;    return (cnt & 1) ? -1 : 1 ;}ll g(ll x){	return qpow(2ll , x - 1) ;}void solve(ll x){	ll ans = 0 ;	for(ll d = 1 ; d * d <= x ; d ++)	{		if(x % d != 0)  continue ;		ans += get_mu(d) * g(x / d) ;		if(d * d != x)		  ans += get_mu(x / d) * g(d) ;		ans %= mod ;	}	ans = (ans + mod) % mod ;	printf("%lld\n" , ans) ;}int main(){	ll x , y ;	scanf("%lld%lld" , &x , &y) ;	if(y % x != 0){printf("0\n") ; return 0 ;}	solve(y / x) ; 	return 0 ;}