Author: lllyouo
Date: 20250702
tag: 约数
link: https://www.luogu.com.cn/problem/P1072

问题描述

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;
}