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

05/12/2016 4 minutes read
Share:

Đề 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 ≤ 106).

Đầ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

Các 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 tôi áp dụng thuật toán tham lam Greedy để tìm ra chìa khóa của bài toán. Tôi 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à tôi 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 tôi 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 tôi ở dưới đây.

Lời giải:

(Các 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 tôi 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 tôi 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 các 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;
}
view raw GGD.cpp hosted with ❤ by GitHub

Code by Phạm Văn Lâm.

Share: