【題解】ZeroJudge d860: NOIP2001 2.最大公约数和最小公倍数问题

【題目敘述】https://nanti.jisuanke.com/t/T2112

Python code (credit: Shawn Chen)

  • 找出两个正整数 P, Q,使 P, Q 以 a 為最大公因數,以 b 為最小公倍數。2≤​a <100000, 2≤ b ​≤1000000。
  • 依題意,
    • P = a * p,Q = a * q,p 與 q 互質。
    • b = a * p * q
  • 令 c = b / a = p * q
    • 從質數表 (prime[ ]) 中枚舉可以整除 c 的 p,共有 j 個數字。
    • 滿足題意的 (P, Q) 個數為 2 ^ j。
# sqrt(1e6 / 2) < 1e3
maxn = 1000
p = [1 for i in range(maxn)]
prime = []
for i in range(2, maxn):
    if p[i] == 1:
        prime.append(i)
        for j in range(i, maxn, i):
            p[j] = 0

while True:
    try:
        a, b = map(int, input().split())
        c = b / a

        if c != int(c):
            print(0)
            break
        j = 0
        for i in prime:
            if c % i == 0:
                j += 1
        print(2 ** j)
    except:
        break

C++ code (credit: Yui Huang)

  • 利用質因數分解找出答案。
  • 【例】GCD a = 3, LCM b = 60
    • b / a = 20 = 2 ^ 2 * 5,共有2,5兩個不同的質因數。(cnt = 2)
    • 由於 b / a 為兩個互質數字的乘積,(P, Q) 共有 2^cnt 種組合。
#include <bits/stdc++.h>
using namespace std;

int a, b, cnt;

int main(){
    cin >> a >> b;
    if (a > b || b % a){
        cout << 0 << "\n";
        return 0;
    }
    b /= a;
    for (int i = 2; i <= b; i++){
        if (b % i == 0){
            while (b % i == 0){
                b /= i;
            }
            cnt++;
        }
    }
    cout << (1<<cnt) << "\n";
}

C++ code (credit: Amy Chou)

  • (P, Q) 兩數,GCD為 x0,LCM為 y0。
  • 令 P = p * x0, Q = q * x0,則 P * Q = p * q * x0 * x0 = x0 * y0。
  • 因為 2≤x0​<100000, 2≤y0​≤1000000,x0 * y0 會超出int的範圍,因此所有變數都宣告成long long。
  • 函式 gcd (x, y):求 x, y 的最大公因數
  • 令 N = x0 * y0,枚舉 P:範圍最小值為 x0,最大值為 sqrt (N)
    • 依題意,N 要能被 P 整除。
    • 依題意,N 與 N / P 的 GCD 為 x0。
    • (P, N/P) 與 (N/P, P) 視為不同解。
#include <iostream>
using namespace std;

long long gcd(long long x, long long y) {
    while ((x %= y) && (y %= x));
    return x + y;
}

int main() {
    long long x0, y0;
    cin >> x0 >> y0;
    if (x0 == y0) {
        cout << "1\n";
    } else {
        long long N = x0 * y0;
        long long ans = 0;
        for (long long P = x0; P*P < N; P++){
            if (N % P == 0 && gcd(P, N/P) == x0){
                ans += 2;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

分享本文 Share with friends