UVA 11388 GCD LCM：構造滿足給定最大公約數與最小公倍數的數對

UVA 11388 GCD LCM 題目解析

給定 G, L，求 a ≤ b 使得 gcd(a,b)=G 且 lcm(a,b)=L。若不存在輸出 -1，多解取 a 最小。

數學結論

對任意正整數 a,b：gcd(a,b) * lcm(a,b) = a * b。
若解存在，必有 gcd(G,L) = G 且 lcm(G,L) = L，即 G 整除 L。此時 a=G, b=L 即為最小 a 解。
證明：設 a=G*a', b=G*b'，gcd(a',b')=1，則 L = G*a'*b'。要使 a 最小，取 a'=1, b'=L/G，即 a=G, b=L。

算法

1. 若 L % G != 0 輸出 -1。
2. 否則輸出 G L。

代碼

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; scanf("%d",&T);
    while (T--) {
        long long G,L; scanf("%lld%lld",&G,&L);
        if (L % G) puts("-1");
        else printf("%lld %lld\n", G, L);
    }
}