原题链接：https://codeforces.com/contest/900/problem/D
求序列a的个数，满足\(\sum_{i=1}^{len}=y\)并且\(gcd(a_1,a_2...a_{len})=x\)
其中序列的长度不限
答案对\(1e9+7\)取模
首先可以分析出，当\(x\)不整除\(y\)时，肯定没有答案
如果\(x\)整除\(y\)时，相当于有\(y\)个球，任务是把这\(y\)个球分成若干份，每一份的个数都是\(x\)的倍数，还要满足所有份的个数的最大公约数是\(x\)
求一共有多少种划分方法
首先计算分法总数
利用插板法
\(n=\frac{x}{y}\)
\(sum=\sum_{i=0}^{n-1}\lgroup_{i}^{n-1}\rgroup=2^{n-1}\)
但是，这里计算出的结果包含了\(gcd\)为\(x\)的倍数的情况
自然而然就考虑到了容斥
这里用到了对我而言新的处理容斥的方法（其实以前遇到过一次，但是没有记录下来）
dp处理容斥
首先处理出\(n\)的所有因数，放在数组a中（a要正序排序）
初始化\(dp_i=2^{\frac{n}{a_i}-1}\)(这里的\(dp_i\)其实和上面的总数一样，包括了倍数的部分)
然后从后往前遍历dp数组（当遍历到i时\(dp_i\)已经被之前的处理变成\(gcd\)只有\(a_i\)的方法数了）
当遍历到i时，枚举前面所有\(a_i\)的倍数\(a_j\)，将\(dp_j\)减去\(dp_i\)
最后dp数组的首项就是答案（只有\(gcd\)为1的方法数）
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
const int mod=1e9+7;
int n,m,x,y,dp[N];
int qmi(int x,int y){
int res=1;
while(y){
if(y&1)res=res*x%mod;
x=x*x%mod;
y>>=1;
}
return res;
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);
cin>>x>>y;
if(y%x){
cout<<"0\n";
return 0;
}
n=y/x;
vector<int>a;
for(int i=1;i*i<=n;i++){
if(n%i==0){
a.push_back(i);
if(i*i!=n)a.push_back(n/i);
}
}
sort(a.begin(),a.end());
for(int i=0;i<a.size();i++)dp[i]=qmi(2,n/a[i]-1);
for(int i=a.size()-1;i>=0;i--){
for(int j=0;j<i;j++){
if(a[i]%a[j]==0){
dp[j]=(dp[j]-dp[i]+mod)%mod;
}
}
}
cout<<dp[0]<<'\n';
}