问有多少个这样的数字序列
所有数的GCD等于x 并且 所有数的和等于y
题解：
非常难有思路啊 看题解后过的。
考虑序列GCD为x的倍数 即GCD = n*x 和当然都为y 这个条件不要忘了
这样我们可以用 容斥原理来递推的计算GCD为n*x的序列个数是多少
怎么计算呢
以样例为例子 3 9
当GCD = 3 的时候 可以有9 / 3 = 3 个3 序列是这样的 3 3 3
那么有三个空 用插板法 可以计算可以插板的方式数位2**(3-1) = 2**2 = 4种
这里解释插板的意义 3|3 3插一个板就表示相邻的数求和 那么3|3 3 就是 6 3
同理 3 3|3 -> 3 6; 3|3|3 -> 9； 但是这样插板出现了问题 就是出现了GCD 并不为3的序列 即 9
这个时候就需要用容斥原理来 递推
设a[i] 表示GCD为i的序列个数， a[j] 表示GCD为j个数
不妨设i > j
if (i % j == 0) a[j] = (a[j]+MOD-a[i]) % MOD; 因为 GCD 为i的情况是一定可以通过插板 得到GCD 为j的情况
而通过从大到小的递推 a[i]已经是容斥后的结果
这样最终得到GCD最小为x 的结果就是答案 网上题解写的有点不太清楚 这里自己补充点自己的理解。轻喷。。
代码君：
1 #include <bits/stdc++.h> 2 #include <string.h> 3 #include <iostream> 4 #include <stdio.h> 5 #define pb push_back 6 7 const int MOD = 1e9+7; 8 const int MAXN = 1e5+7; 9 typedef long long ll; 10 11 using namespace std; 12 13 ll x, y; 14 15 ll mypow(ll base, ll p) 16 { 17 if (p == 0) return 1; 18 ll tmp = mypow(base, p/2); 19 if (p & 1) tmp = (tmp*tmp*base) % MOD; 20 else tmp = (tmp*tmp) % MOD; 21 return tmp; 22 } 23 vector<ll> a; 24 ll dp[MAXN]; 25 int main() 26 { 27 //freopen("in.txt", "r", stdin); 28 while (cin >> x >> y) 29 { 30 a.clear(); 31 if (y % x != 0) 32 { 33 cout << 0 << endl; 34 continue; 35 } 36 for (ll i = 1; i*i <= y; i++) 37 { 38 if (i % x == 0 && y % i == 0) a.pb(i); 39 if (i*i != y && y % i == 0 && (y/i)%x==0 ) a.pb(y/i); 40 } 41 sort(a.begin(), a.end()); 42 for (int i = 0; i < a.size(); i++) dp[i] = mypow(2, (y/a[i]-1)); 43 for (int i = (int)a.size()-1; i >= 0; i--) 44 for (int j = i+1; j < a.size(); j++) 45 if (a[j] % a[i] == 0) 46 { 47 dp[i] -= dp[j]; 48 dp[i] = (dp[i] + MOD) % MOD; 49 } 50 cout << dp[0] << endl; 51 } 52 return 0; 53 }