（未完待续）一道神奇的题目，有多种解法。

题目链接：CodeForces 900D。

题目

题目描述

给出 $x,y$，求有多少个数列满足其 $\gcd$ 为 $x$，和为 $y$，答案对 $10^9+7$ 取模。

数据范围

时空限制

题解

首先显然可以看出 $x\nmid y$ 时显然无解，答案转化为：

有多少个数列满足其 $\gcd$ 为 $1$，和为 $\frac{y}{x}$，答案对 $10^9+7$ 取模。

正难则反，我们先忽略 $\gcd=1$ 的约束条件，我们不妨设 $g(x)$ 表示数列和为 $x$ 的正整数数列的个数，那么我们有：

$$
\begin{aligned}
g(x)&=\sum _ {i=1}^x[\sum _ {j=1}^{i}a _ j=x]\\
&=\sum _ {i=1}^x\binom{x-1}{i-1}\\
&=\sum _ {j=0}^{x-1}\binom{x-1}{j}1^j1^{x-j-1}\\
&=2^{x-1}
\end{aligned}
$$

我们再用 $g(x)$ 表示 $f(x)$，其中 $f(x)$ 表示满足其 $\gcd$ 为 $1$，和为 $\frac{y}{x}$ 的数列个数。

$$g(x)=\sum _ {d\mid x}f(\frac{x}{d})$$

下面有多种解法求解答案。

解法 A（莫比乌斯反演）

看到上面那个式子很眼熟，用莫比乌斯反演就行了，得到：

$$f(x)=\sum _ {d\mid x}\mu(d)g(\frac{x}{d})$$

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define MOD 1000000007

ll x,y;

const int MAXSIZE=100000+5;

bool vis[MAXSIZE];
int tot,prime[MAXSIZE];

inline void Init(reg int n){
    for(reg int i=2;i<=n;++i){
        if(!vis[i])
            prime[++tot]=i;
        for(reg int j=1;j<=tot&&(ll)i*prime[j]<=n;++j){
            vis[i*prime[j]]=true;
            if(i%prime[j]==0)
                break;
        }
    }
    return;
}

inline ll mu(reg ll x){
    reg int sum=0;
    for(reg int i=1;i<=tot&&(ll)prime[i]*prime[i]<=x;++i)
        if(x%prime[i]==0){
            reg int cnt=0;
            while(x%prime[i]==0)
                x/=prime[i],++cnt;
            if(cnt>1)
                return 0;
            sum+=cnt;
        }
    if(x>1)
        ++sum;
    return (sum&1)?(MOD-1):(1);
}

inline ll pow(reg ll x,reg ll exp,reg ll mod){
    reg ll res=1;
    while(exp){
        if(exp&1)
            res=res*x%mod;
        x=x*x%mod;
        exp>>=1;
    }
    return res;
}

int main(void){
    scanf("%lld%lld",&x,&y);
    if(y%x!=0){
        puts("0");
        return 0;
    }
    Init(1e5);
    reg int n=y/x;
    ll ans=0;
    for(reg int i=1;(ll)i*i<=n;++i)
        if(n%i==0){
            ans=(ans+(ll)mu(n/i)*pow(2,i-1,MOD)%MOD)%MOD;
            if(i*i!=n)
                ans=(ans+(ll)mu(i)*pow(2,n/i-1,MOD)%MOD)%MOD;
        }
    printf("%lld\n",ans);
    return 0;
}

解法 B（容斥）

解法 C（递归）