题目

200. Hankson的趣味题

算法标签: 数论, 最大公约数, 最小公倍数, 约数

思路

因为$[x,a_0]=b_1$因此$x$一定是$b_1$约数, 注意到, 数据范围是$2\times 10^9$如果直接使用试除法计算约数时间复杂度是$O(n\sqrt{n})$会超时, 因此需要进行优化,
可以将$1\sim \sqrt{n}$之间的质数全部预处理出来, 然后将$b_1$转化为算数基本定理形式 因为在$int$范围内约数个数最多的数的约数个数大约是$1600$个, 因此有效降低了时间复杂度

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
//预处理的质数的个数和约数个数
const int N = 50000, M = 100;

int primes[N], cnt;
bool vis[N];
PII factor[M];
int f_cnt;
int divs[N], d_cnt;

void get_primes() {
    for (int i = 2; i < N; ++i) {
        if (!vis[i]) primes[cnt++] = i;
        for (int j = 0; (LL) primes[j] * i < N; ++j) {
            vis[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

void dfs(int u, int curr) {
    if (u > f_cnt) {
        divs[d_cnt++] = curr;
        return;
    }
    for (int i = 0; i <= factor[u].second; ++i) {
        dfs(u + 1, curr);
        curr *= factor[u].first;
    }
}

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    get_primes();

    int n;
    cin >> n;
    while (n--) {
        // (x, a0) = a1, [x, b0] = b1
        int a0, a1, b0, b1;
        cin >> a0 >> a1 >> b0 >> b1;

        // 分解质因数
        int val = b1;
        f_cnt = 0;
        for (int i = 0; primes[i] <= val / primes[i]; ++i) {
            if (val % primes[i] == 0) {
                int c = 0;
                while (val % primes[i] == 0) val /= primes[i], c++;
                factor[++f_cnt] = {primes[i], c};
            }
        }
        if (val > 1) factor[++f_cnt] = {val, 1};

        // 求b1的所有约数
        d_cnt = 0;
        dfs(1, 1);
        int ans = 0;

        //枚举所有约数, 判断是否符合条件
        for (int i = 0; i < d_cnt; ++i) {
            int x = divs[i];
            if (gcd(x, a0) == a1 && ((LL) x * b0 / gcd(x, b0)) == b1) ans++;
        }
        cout << ans << "\n";
    }


    return 0;
}