原题链接:Acwing200

题目描述:给定 $4$ 个正整数 $a,b,c,d$,求满足 $(x,a)=b$ 且 $[x,c]=d$ 的 $x$ 个数。数据保证 $b \mid a$ 且 $c \mid d$。共 $n$ 组测试数据。

数据范围:$1≤n≤2000, 1≤a,b,c,d≤2 \times 10^9$

线性筛法,欧几里得算法,约数,搜索

比较显然的做法是,枚举 $d$ 的所有约数 $x$,再判定 $x$ 是否合法,统计合法数量即可。

朴素做法

如果考虑用试除法求约数个数,时间复杂度 $O(\sqrt{d} \approx 5 \times 10^4)$,如果我们处理出了 $d$ 的所有约数,那么只需要通过 $gcd$ 判定合法,复杂度可以认为是 $O(logx)$ ,因此本题瓶颈在于求 $d$ 的约数。如果不进行优化,复杂度约为:$2000 \times 5 \times 10^4 = 10^8$,而时限只有 $300ms$。

优化做法

在 $2 \times 10^9$ 范围内约数个数最多只有 $1536$,远小于 $5 \times 10^4$,我们希望通过更快的方式找到这些约数。$5 \times 10^4$ 以内的质数数量大约为 $\frac{50000}{ln50000} \approx 5000$,因此用质数试除,可以将试除的复杂度降低 $10$ 倍,我们再用 $d$ 的质因子组合,即暴搜出 $d$ 的所有约数(约数个数很少,暴搜复杂度很小)。最后再枚举所有 $d$ 的约数进行判断即可,判断的时间复杂度 $O(2000 \times 1600 \times logx)$,线性筛法 $O(10^5)$。总时间复杂度大约为 $10^7$。

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

const int N = 50010;

int n, a, b, c, d, t;
int primes[N], cnt;
bool st[N];
PII fac[1600];
int fac_cnt;
int divs[N], div_cnt;

void euler(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] <= n / i; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

void dfs(int u, int val) {
    if (u == fac_cnt) {
        divs[div_cnt++] = val;
        return;
    }
    // 枚举第u个质因子选几个
    for (int i = 0; i <= fac[u].second; i++) {
        dfs(u + 1, val);
        val *= fac[u].first;
    }
}

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

int main() {
    euler(N - 1);
    cin >> n;
    while (n--) {
        scanf("%d%d%d%d", &a, &b, &c, &d);
        // 对d分解质因数,优化方式,用质数试除
        fac_cnt = div_cnt = 0, t = d;
        for (int i = 0; primes[i] <= t / primes[i]; i++) {
            if (t % primes[i] == 0) {
                int s = 0;
                while (t % primes[i] == 0) t /= primes[i], s++;
                fac[fac_cnt++] = {primes[i], s};
            }
        }
        if (t > 1) fac[fac_cnt++] = {t, 1};
        // 暴搜出d的所有约数
        dfs(0, 1);
        // 枚举d的所有约数x,找出符合限制条件的答案数量
        int res = 0;
        for (int i = 0; i < div_cnt; i++) {
            int x = divs[i];
            if (gcd(a, x) == b && (1ll * c * x / gcd(c, x)) == d) res++;
        }
        cout << res << endl;
    }
    return 0;
}