CF 1499D（数学，筛法）

对于任意一个$(a,b)，$令 $l = lcm(a,b), ~g = gcd(a,b)$，则必然有 $g|l$。

那么两边同除 $g$，我们有

$$c \times \frac{l}{g} - d = \frac{x}{g}$$

这说明： $g|x$

所以我们可以枚举 $x$的所有因子 $g$ （例如 $x = 12$，因子有 $g=1,2,3,4,6,12$），当我们已知 $g = gcd(a,b)$ 时，$l = lcm(a,b)$ 也可以计算出来。

怎么枚举 $x$ 的所有因子 $g$？

for (int g = 1; g * g <= x; g++) {
    if (x % g == 0) {
        cal(g);
        if (x/g != g) cal(x/g);
    }
}

问题转化为：已知 $gcd(a,b), ~ lcm(a,b)$，如何求满足条件的 $(a,b)$ 数量？

发现 $gcd$ 为所有质因子的 $\min$，而 $lcm$ 为所有质因子的 $\max$。

所以对于 $lcm(a,b)$ 的每一个质因子 $p_i$，看一下 $p_i$ 在 $lcm(a,b)$ 中出现的次数是否大于它在 $gcd(a,b)$ 中出现的次数即可。

如果大于，我们可以将这个质因子 出现次数较小的分配给 $a$，或者给 $b$，所以答案乘上 $2$。

如果等于，则这个质因子没有贡献，答案不变。

实现过程中，直接令 $r = \frac{lcm(a,b)}{gcd(a,b)}$，然后看一下 $r$ 有多少个质因子就可以了。

设 $r$ 的质因子数量为 $m$，则 $ans = 2^m$

快速求 $r$ 的质因子数量，我们可以预处理出 每一个数的质因子数量，但是数组的上限 maxn 是多少？

注意到 $c\times r - d = \frac{x}{g}$，所以 $r = \frac{x}{gc} + \frac{d}{c}$，分母最小的情况下，$g = c = 1$，所以 $r = (x + d) \leq 2\times10^7$，只要预处理 maxn <= 2e7 的部分即可。

怎么预处理出每一个数的质因子数量？

有两种方法，比较简单的是直接用 Eratosthenes 筛法，还有一种是欧拉筛 + dp。

法一：Eratosthenes 筛法

int sum[maxn];  // 每个数的质因子出现个数
void init() {
    for (int i = 2; i <= maxn-5; i++) {
        if (sum[i] == 0) {  // i为质数
            for (int j = i; j <= maxn-5; j += i)
                sum[j]++;
        }
    }
}

因为 $j$ 是从 $i$ 开始的，所以复杂度为 $O(n\log n)$

• 注: 如果无需计算质因子数量，只需要筛质数的话，直接从 int j = i * i 开始即可，这样的复杂度为 $O(n \log \log n)$

法二：欧拉筛 + dp

bool p[maxn];
vector<int> primes;
 
void init() {
    fill(p, p+maxn, 1);
    p[1] = 0;
    sum[2] = 1;
    for (int i = 2; i <= maxn-5; i++) {
        if (p[i]) {
            primes.push_back(i);
            sum[i] = 1;
        }
 
        for (int j = 0; j < primes.size(); j++) {
            int cur = primes[j];
            ll tar = cur * i;
            if (tar >= maxn) break;

            p[tar] = 0;
            sum[tar] = sum[i];  // dp，继承之前的质数数量
            if (i % cur) sum[tar]++;  // 如果 i 和 cur互质，说明 cur 是一个没用过的质数
            if (i % cur == 0) break;
        }
    }
}

复杂度：$O(n)$

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e7+5;

int gcd(int a, int b) {
    if (!b) return a;
    return gcd(b, a%b);
}
 
int sum[maxn];

ll a,b,x,ans = 0;
void cal(ll g) {
    ll l = (b*g + x);
    if (l % (a * g)) return;
    ans += (1LL << (sum[l/(a*g)]));
}
 
bool p[maxn];
vector<int> primes;
 
void init() {
    fill(p, p+maxn, 1);
    p[1] = 0;
    sum[2] = 1;
    for (int i = 2; i <= maxn-5; i++) {
        if (p[i]) {
            primes.push_back(i);
            sum[i] = 1;
        }
 
        for (int j = 0; j < primes.size(); j++) {
            int cur = primes[j];
            ll tar = cur * i;
            if (tar >= maxn) break;
            p[tar] = 0;
            sum[tar] = sum[i];
            if (i % cur) sum[tar]++;
            if (i % cur == 0) break;
        }
    }
}
 
int main() {
    int T; cin >> T;
    init();
 
    while (T--) {
        cin >> a >> b >> x;
        ans = 0;
 
        for (int g = 1; g * g <= x; g++) {
            if (x % g == 0) {
                cal(g);
                if (x/g != g) cal(x/g);
            }
        }
        cout << ans << "\n";
    }
}