洛谷P1072 Hankson的趣味题

问题描述

link

分析

略

参考代码

#include <bits/stdc++.h>
using namespace std;

vector<long long> factorize(long long n) {
    vector<long long> factor;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            factor.push_back(i);
            if (i != n / i) factor.push_back(n / i);
        }
    }

    return factor;
}

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

long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;
}

int main() {
    int t; cin >> t;
    while (t--) {
        long long a0, a1, b0, b1;
        cin >> a0 >> a1 >> b0 >> b1;

        auto v = factorize(b1);

        int cnt = 0;
        for (int i = 0; i < v.size(); i++) {
            long long x = v[i];
            if (gcd(a0, x) == a1 && lcm(b0, x) == b1) cnt++;
        }
        cout << cnt << endl;
    }

    return 0;
}

优化代码

#include <bits/stdc++.h>
using namespace std;

vector<long long> factorize(long long n) {
    vector<long long> factor;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            factor.push_back(i);
            if (i != n / i) factor.push_back(n / i);
        }
    }

    return factor;
}

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

bool check(long long a, long long b) {
    return gcd(a, b) == 1;
}

int main() {
    int t; cin >> t;
    while (t--) {
        long long a0, a1, b0, b1;
        cin >> a0 >> a1 >> b0 >> b1;

        if (b1 % a1) {
            cout << 0 << endl;
            continue;
        }

        auto v = factorize(b1 / a1);

        int cnt = 0;
        for (int i = 0; i < v.size(); i++) {
            long long x = v[i];
            if (check(a0 / a1, x) && check(b1 / a1 / x, b1 / b0)) cnt++;
        }
        cout << cnt << endl;
    }

    return 0;
}