前置推导
令 \(b_1 = \frac{a_1}{x},b_2 = \frac{a_2}{x},\dots,b_n = \frac{a_n}{x}\) 。
很显然 \(b_i\) 为整数，且 \(b\) 数组的全部元素互质，即 \(gcd(b_1,b_2,b_3,\dots,b_n) = 1\)。
因为
\[\sum_{i = 1}^{n} a_i = y \]所以
\[x\times\sum_{i = 1}^{n} b_i = y \]\[\sum_{i = 1}^{n} b_i = \frac{y}{x} \]根据 \(整数\) \(+\) $ 整数 $ \(=\) \(整数\) 的封闭法则且 \(b_i\) 为整数，可得 \(\frac{y}{x}\) 也是整数。所以当 \(x \nmid y\) 时一定无解。
令 $ m = \frac{y}{x} $，则
\[\sum_{i = 1}^{n} b_i = m \]大致思路
我们现在的目标是求出 \(b\) 数组，满足所有元素互质。直接这样看上去很难求，我们考虑正难则反，利用容斥原理解决，即先假设 \(b\) 数组中的元素不一定满足两两互质的个数，然后计算出 \(gcd(b_1,b_2,\dots,b_n) = d\) 且 \(d \ne 1\) 的个数。再用总个数减去不满足条件的个数就是满足条件的个数。
总个数
先来计算总个数，显然我们当前求解的问题相当于求 \(m\) 的所有本质不同的拆分总方案数。
因为
\[m = \underbrace{1 + 1 + \dots + 1}_{m} \]所以可以考虑插板法，设当前要把 \(m\) 拆为 \(i\) 个数相加，所以此时方案数为$ \binom{m - 1}{i - 1} $。
方法 \(1\)(暴力)
所以总方案数为
\[\sum_{i = 1}^{m} \binom{m - 1}{i - 1} \]根据二项式定理
\[(a+b)^n = \sum_{i = 0}^{n} \binom{n}{i} \times a^{n - i}\times b^{i} \]令
\[a = 1,b = 1 \]则
\[\sum_{i = 0}^{m - 1} \binom{m - 1}{i} \times 1 \times 1 = \sum_{i = 1}^{m} \binom{m - 1}{i - 1} \]所以
\[\sum_{i = 1}^{m} \binom{m - 1}{i - 1} = (1 + 1)^{m - 1} = 2^{m - 1} \]方法 \(2\)（人类智慧）
因为空位只有选和不选两种情况，一共有 \(m - 1\) 个空位，所以总方案数为 \(2 ^ {m - 1}\)
不满足条件的个数
令函数 $f(x) $ 表示 $ \sum_{i = 1}^{n} b_i = x $ 且 \(gcd(b_1,b_2,b_3,\dots,b_n) = 1\) 的个数。考虑怎么递推 \(f(x)\)，我们很容易地发现和为 \(m\) 且 \(gcd(b_1,b_2,b_3,\dots,b_n) = d\) 的个数为 \(f(\frac{m}{d})\)显然 \(d|m\)。
所以
\[\sum_{d|x} f(\frac{x}{d}) = 2 ^ {x - 1} \]再根据容斥原理得
\[f(x) = 2^{x - 1} - \sum_{d|x,d \ne 1} f(\frac{x}{d}) \]即
\[f(x) = 2^{x - 1} - \sum_{d|x,d \ne x} f(d) \]求解
递归求解 $ f(x) $ 即可。
时间复杂度 \(\mathcal{O}(\sqrt{n})\)
\(Code\)
#include <bits/stdc++.h>
#define int long long
#define Add(x, y) x = add(x, y)
#define Mul(x, y) x = mul(x, y)
std :: map <int, int> ans;
int x, y; const int mod = 1e9 + 7;
int mul(int x, int y) { return x * y % mod; }
int add(int x, int y) { return (x + y) % mod; }
int qpow(int x, int y) {
int ans = 1; while(y) {
if(y & 1) ans = mul(ans, x);
x = mul(x, x), y >>= 1;
} return ans;
}
int calc(int o) {
if(o == 1) return 1;
if(ans[o]) return ans[o];
int res = calc(1);
for(int i = 2; i * i <= o; ++ i) {
if(o % i) continue;
Add(res, add(calc(i), (i * i != o) * calc(o / i)));
} return ans[o] = add(qpow(2, o - 1), -res);
}
signed main() {
scanf("%lld%lld", &x, &y);
if(y % x) return puts("0");
printf("%lld", add(mod, calc(y / x)));
}