如果 \(y\) 不是 \(x\) 的倍数,答案为 \(0\)。
否则计算有多少种数列满足所有数 \(\gcd\) 为 \(1\) 且和为 \(\frac{y}{x}\)。
定义 \(f_i\) 表示和为 \(i\) 且 \(\gcd\) 为 \(1\) 的数列的数量。
显然有如下等式:
\[2^{x-1}=\sum\limits_{d\mid x}f_d
\]
其中 \(2^{x-1}\) 是和为 \(x\) 的数列的个数。
稍微转化一下为:
\[f_x=2^{x-1}-\sum\limits_{d\mid x,d<x}f_d
\]
然后记忆化搜索就行了。
复杂度玄学,但能过。
code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll x,y;
map<int,int>mp;
ll ksm(ll x,ll y){
ll res=1;
while(y){
if(y&1)res=res*x%mod;
y>>=1;
x=x*x%mod;
}
return res;
}
ll solve(ll t){
if(mp.count(t))return mp[t];
ll ans=1;
for(ll i=2;i*i<=t;++i){
if(t%i==0){
ans=(ans+solve(i))%mod;
if(t!=i*i)ans=(ans+solve(t/i))%mod;
}
}
return mp[t]=(ksm(2,t-1)-ans+mod)%mod;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>x>>y;
mp[1]=1;
if(y%x)cout<<0<<endl;
else cout<<solve(y/x)<<endl;
return 0;
}