SPOJ.COM - Thuật toán bài GGD - Mr Toothless and His GCD Operatione

Đề bài:

Bạn được cho một số N và bạn phải tìm ra hai số a và b sao cho GCD(a, b) (ước chung lớn nhất của a và b) là lớn nhất có thể. Trong đó 1<=a<b<=N.

Đầu vào

Bắt đầu với số T (<= 100) - là số lượng test case. Mỗi test case sẽ bao gồm một số N duy nhất (2 ≤ N ≤ 10⁶).

Đầu ra

Với mỗi test case, in ra hai số a và b thỏa mãn. Nếu có nhiều test case thỏa mãn thì in ra cặp a và b thỏa mãn a + b là lớn nhất.

Ví dụ

Đầu vào:

1 2 

Đầu ra:

Case 1: 1 2 

Bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://www.spoj.com/problems/GGD/

Problem Setter: Md Abdul Alim, Department of CSE, Bangladesh University of Business & Technology

Phân tích

• Trước tiên mình áp dụng thuật toán tham lam Greedy để tìm ra chìa khóa của bài toán. Mình nhận ra rằng để ước chung lớn nhất của 2 số a và b là lớn nhất thì 2 số đó phải thỏa mãn là b = 2*a. Lúc này thực chất là mình phải tìm ra số a lớn nhất thỏa mãn b = 2*a.

• Để làm được điều này một cách nhanh nhất mình sẽ áp dụng thuật toán chia để trị Divide and Conquer để giải quyết được nhanh hơn. Đối với việc áp dụng phương pháp chia để trị này thì việc đầu tiên phải xác định biên của kết quả. Rõ ràng giá trị của số a sẽ là từ 1 đến N. Việc tiếp theo chỉ là triển khai thuật toán chia để trị. Xin mời bạn theo dõi cách triển khải của mình ở dưới đây.

Lời giải

Bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của mình nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code mình viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của bạn.

Code C/C++

#include <iostream>
using namespace std;

int N;					// Lưu số N đầu vào
int Num1, Num2;			// Lần lượt là 2 số được chọn

bool IsValid(int mid)
{
	int a = mid, b = mid*2;
	if(b <= N)
	{
		Num1 = a;
		Num2 = b;
		return true;
	}
	return false;
}

int main()
{
	// freopen("input.txt","r",stdin);
	int T;
	cin >> T;
	for(int tc = 0; tc < T; tc++)
	{
		cin >> N;
		if(N == 2) cout << "Case " << tc + 1 << ": 1 2" << endl;
		else if(N == 3) cout << "Case " << tc + 1 << ": 2 3" << endl;
		else
		{
			// Dùng phương pháp chia đôi để tìm ra giá trị lớn nhất của UCLN
			// UCLN sẽ nằm trong khoảng từ 1 đến N
			int Left = 1, Right = N, Mid = 0;
			while(Left < Right - 1)
			{
				Mid = (Left + Right) / 2;
				if(IsValid(Mid)) Left = Mid;
				else Right = Mid - 1;
			}
		if(IsValid(Right)) cout << "Case " << tc + 1 << ": " << Num1 << " " << Num2 << endl;
		else if(IsValid(Left)) cout << "Case " << tc + 1 << ": " << Num1 << " " << Num2 << endl;
		}
	}
	return 0;
}