(未完待续)一道神奇的题目,有多种解法。
题目链接:CodeForces 900D。
题目
题目描述
给出 $x,y$,求有多少个数列满足其 $\gcd$ 为 $x$,和为 $y$,答案对 $10^9+7$ 取模。
数据范围
变量 | 数据范围 |
---|---|
$x,y$ | $1\leq n\leq 10^9$ |
时空限制
题目编号 | 时间限制 | 空间限制 |
---|---|---|
CodeForces 900D | $1\text{s}$ | $256\text{MiB}$ |
题解
首先显然可以看出 $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;
}
近期评论