题目链接

题意

给定正整数 $c,d,x$,求正整数pair $(a,b)$ 的数量使得 $$c \times lcm(a,b) - d \times gcd(a,b) = x$$

其中,共 $T \leq 10^4$ 个testcase,$1 \leq c,d,x \leq 10^7$

• $(a,b)$ 和 $(b,a)$ 不同,例如 $(1,6), (6,1)$ 算两个,但是 $(3,3),(3,3)$ 算一个。

题解

对于任意一个$(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)$

法二:欧拉筛 + 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";
    }
}