ZeroJudge 解題筆記：d256. 11388 - GCD LCM

作者：王一哲
日期：2026年5月15日


ZeroJudge 題目連結：d256. 11388 - GCD LCM

解題想法

假設兩個數字 $a, b$ 的最大公因數 $G = GCD(a, b)$，最小公倍數 $L = LCM(a, b)$，而且題目要求「如果有多組解，輸出 $a$ 最小的一組」，答案就是 $a = G$，$b = L$，因為 $a$ 之中不能有 $G$ 以外大於 $1$ 的因數。如果 $L$ 不能被 $G$ 整除，則輸出 $-1$。

Python 程式碼

使用時間約為 15 ms，記憶體約為 8.8 MB，通過測試。

T = int(input())
for _ in range(T):
    G, L = map(int, input().split())
    if L%G != 0: print("-1")
    else: print(G, L)

C++ 程式碼

使用時間約為 1 ms，記憶體約為 1.5 MB，通過測試。

#include <cstdio>

int main() {
    int T; scanf("%d", &T);
    for(int t=0; t<T; t++) {
        int G, L; scanf("%d %d", &G, &L);
        if (L%G != 0) puts("-1");
        else printf("%d %d\n", G, L);
    }
    return 0;
}