d256 - 11388 - GCD LCM

🔗 前往 ZeroJudge 原題

題目描述

題目要求找出兩個正整數 a 和 b，使得它們的最大公因數 (GCD) 為 G，最小公倍數 (LCM) 為 L。如果存在多組解，則輸出 a 最小的那組。如果無解，則輸出 -1。

解題思路

根據 GCD 和 LCM 的關係，我們知道 a * b = GCD * LCM。因此，我們可以通過判斷 LCM 是否能被 GCD 整除來確定是否存在解。如果 LCM 不能被 GCD 整除，則無解。如果 LCM 可以被 GCD 整除，則 a 和 b 必然存在。由於題目要求 a 最小，我們可以令 a = GCD，然後計算 b = LCM / GCD。如果 b 是整數，且 a <= b，則輸出 a 和 b。

複雜度分析

• 時間複雜度: O(T)
• 空間複雜度: O(1)

程式碼

#include <iostream>
using namespace std;
int main(){
	int t,a,b;
	cin >> t;
	while(t--){
		cin >> a >> b;
		if(b%a)
			cout << "-1\n";
		else
			cout << a << " " << b << "\n"; 
	}
}