求滿足 GCD=n, LCM=m 的正整數對個數 (數學推導 + 枚舉因數)

問題描述

給定 n, m (1 ≤ n,m ≤ 10¹⁰)，求有多少對正整數 (a,b) 使得 gcd(a,b)=n 且 lcm(a,b)=m。

數學轉化

• 設 a = n·x, b = n·y，則 gcd(x,y)=1, lcm(x,y)=m/n。
• 因 gcd(x,y)·lcm(x,y) = x·y，得 x·y = m/n。
• 問題轉化為：在 1~m/n 中找互質因數對 (x,y) 使得 x·y = m/n。

解法

若 m 不能被 n 整除，答案為 0。否則令 t = m/n。枚舉 i 從 1 到 √t，若 i 整除 t，設 j = t/i。若 gcd(i,j)=1，則 (i,j) 為一組合法解。因 (x,y) 有序，每組計 1 次（若 i≠j 則 (j,i) 另計，但題目通常視為無序對，需確認；此處代碼計無序對）。

代碼 (C++)

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

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

int main() {
    int T; cin >> T;
    while (T--) {
        ll n, m; cin >> n >> m;
        if (m % n) { cout << 0 << '\n'; continue; }
        ll t = m / n;
        int ans = 0;
        for (ll i = 1; i*i <= t; ++i) {
            if (t % i == 0) {
                ll j = t / i;
                if (gcd(i, j) == 1) ++ans;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

複雜度

O(√(m/n) · log max) 每測試用例，滿足 10¹⁰ 範圍。