P1001 最大公约数与最小公倍数问题

洛谷 P1029 [NOIP 2001 普及组] 最大公约数和最小公倍数问题

题解

显然有 \(x_0 y_0 = PQ\)，只需枚举 \(x_0 y_0\) 的因数即可。

可以发现，一个正整数 \(a\) 的因数是关于 \(\sqrt{a}\) 对称的，因为超过 \(\sqrt{a}\) 的 \(a\) 的因数 \(x\) 一定可以存在一个小于 \(\sqrt{a}\) 的正整数 \(y\)，使得 \(xy = a\)。那么只需枚举小于等于 \(\sqrt{x_0 y_0}\) 的因数即可得到 \(x_0 y_0\) 的所有因数，这部分的时间复杂度是 \(O(\sqrt{x_0 y_0})\)。

参考代码

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

int x, y;

ll gcd(ll a, ll b){
    if(a % b == 0)
        return b;
    return gcd(b, a % b);
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> x >> y;
    ll tmp = x * y, cnt = 0;
    for(ll i = x; i <= tmp; i += x){
        if(tmp % i != 0)
            continue;
        ll j = tmp / i;
        if(i * j / gcd(i, j) == y)
            cnt++;
    }
    cout << cnt;

    return 0;
}