CF1499D The Number of Pairs 题解 线性筛

题目链接：https://codeforces.com/problemset/problem/1499/D

题目大意：

给你三个整数 \(c, d, x\)（\(1 \le c,d,x \le 10^7\)），问：存在多少对正整数对 \((a, b)\) 满足：

其中，\(lcm(a, b)\) 表示整数 \(a\) 和 \(b\) 的最大公约数，\(gcd(a, b)\) 表示整数 \(a\) 和 \(b\) 的最小公倍数。

解题思路：

令 \(gcd(a, b) = k\)，\(a = Ak, b = Bk\)，且 \(gcd(A, B) = 1\)

则等式

\(c \cdot lcm(a, b) - d \cdot gcd(a, b) = x\)

可以转成

\(cABk - dk = x\)

\(cAB - d = \frac{x}{k}\)

即 \(k \ |\ x\)

所以我们可以 \(O(\sqrt{x})\) 枚举 \(x\) 的因数 \(k\)。

在 \(k\) 确定是，令 \(y = \frac{x}{k} + d\)，则

\(cAB = y\)

\(AB = \frac{y}{c}\)

又因为 \(A\)，\(B\) 是互质的（\(gcd(A,B) = 1\)），所以

设 \(\frac{y}{c}\) 的不同质因子个数为 \(z\)，则\((A, B)\) 有 \(2^k\) 个。

总时间复杂度 \(O(t \sqrt{x})\)。

当时需要先线性筛求出 \(2 \cdot 10^7\) 范围内每个数的不同质因子个数。

示例程序：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e7 + 5;
int prime[maxn/10], cnt, num[maxn];
bool isp[maxn];

void init(int n) {
    for (int i = 2; i <= n; i++) {
        if (!isp[i])
            prime[cnt++] = i, num[i] = 1;
        for (int j = 0; j < cnt && i * prime[j] <= n; j++) {
            isp[ i * prime[j] ] = true;
            if (i % prime[j])
                num[ i * prime[j] ] = num[i] + 1;
            else {
                num[ i * prime[j] ] = num[i];
                break;
            }
        }
    }
}

long long cal(int c, int d, int x) {
    long long ans = 0;
    vector<int> vec;
    for (int i = 1; i * i <= x; i++) {
        if (x % i == 0) {
            vec.push_back(i);
            if (i * i < x)
                vec.push_back(x/i);
        }
    }
    for (auto k : vec) {
        int y = x / k + d;
        if (y % c == 0) {
            ans += 1LL << num[y/c];
        }
    }
    return ans;
}

int T, c, d, x;

int main() {
    init(2e7);
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &c, &d, &x);
        printf("%lld\n", cal(c, d, x));
    }
    return 0;
}