基础数学算法-Hankson的趣味题

题目-Hankson的趣味题(分解质因数 + dfs优化生成约数)

问题分析

给定$a,b,c,d$, 使得$\gcd (x,a)=b,[c,x]=d$, 求$x$的个数
暴力的做法是枚举最小公倍数$d$的所有约数$t$, 然后判断$\gcd (t,a)=b$是否成立
算法时间复杂度瓶颈在枚举约数$O(\sqrt{d})$, 假设$d$是两个很大的质数相乘, 并且$n=2000$的情况下, 总的时间复杂度$O(n\sqrt{d})=10^8$会超时

需要进行优化, 可以尝试对$d$分解质因数, 再$dfs$生成约数, 然后再进行判断, 理论能优化到$10^7$

算法步骤

尝试计算出$d$的所有约数(d的所有约数都是$\le \sqrt{d}$), 通过$gcd$算法比较结果是否正确

代码实现

朴素版暴力枚举$d$约数的实现

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 50010;

int T;
int a, b, c, d;

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

LL lcm(LL a, LL b) {
   
    LL d = gcd(a, b);
    return a * b / d;
}

void solve() {
   
    cin >> a >> b >> c >> d;

    int ans = 0;
    for (int i = 1; i <= d / i; ++i) {
   
        int x, y;
        if (d % i == 0) {
   
            x = i;
            y = d / x;
            if (lcm(x, c) == d && gcd(x, a) == b) ans++;
            if (y != x && lcm(y, c) == d && gcd(y, a) == b) ans++;
        }
    }

    cout << ans << '\n';
}


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

    cin >> T;
    while (T--) solve();

    return 0;
}

分解质因数优化后的代码, 注意在分解质因数的时候需要另外开一个变量$t$, 否则后续判断会产生错误

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;
const int N = 50010;

int T;
int a, b, c, d;
int primes[N], cnt;
bool st[N];
PII facts[N];
int f_cnt;
int divs[N], d_cnt;

void init(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[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

void dfs(int u, int curr) {
   
    if (u == f_cnt) {
   
        divs[d_cnt++] = curr;
        return;
    }

    int p = facts[u].first;
    for (int i = 0; i <= facts[u].second; ++i) {
   
        dfs(u + 1, curr);
        curr *= p;
    }
}

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

LL lcm(LL a, LL b) {
   
    LL d = gcd(a, b);
    return (a / d) * b;
}

void solve() {
   
    f_cnt = d_cnt = 0;
    cin >> a >> b >> c >> d;

    int t = d;
    for (int i = 0; primes[i] <= t / primes[i]; ++i) {
   
        int p = primes[i];
        if (t % p == 0) {
   
            int s = 0;
            while (t % p == 0) s++, t /= p;
            facts[f_cnt++] = {
   p, s};
        }
    }
    if (t > 1) facts[f_cnt++] = {
   t, 1};

    dfs(0, 1);

    int ans = 0;
    for (int i = 0; i < d_cnt; ++i) {
   
        int x = divs[i];
        if (gcd(x, a) == b && lcm(x, c) == d) ans++;
    }

    cout << ans << '\n';
}

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

    init(N - 1);

    cin >> T;
    while (T--) solve();

    return 0;
}