Hướng dẫn giải Đề thi tuyển sinh lớp 10 chuyên Tin trường Phổ Thông Năng Khiếu, năm học 2020 - 2021
Test chấm thử đã có. Các bạn liên hệ fb Coder Nhí để tạo tài khoản chấm thử nhé.
---
Bài 1. PAIRLCM Cặp số
Xét 2 số nguyên dương a, b
Gọi u là ước chung lớn nhất của a, b : u = gcd(a, b)
Gọi k là bội chung nhỏ nhất của a, b : k = lcm(a,b ) = a * b / u
Nhắc lại bài toán ta cần tìm cặp số a, b sao cho lcm(a, b) max hay (a * b / u) max
Xét (a * b / u) max khi (a * b) max và u min. Trong đó U là ước chung lớn nhất của 2 số nguyên dương, nên giá trị min nhất chỉ có thể là 1, khi đó ta nói a, b là 2 số nguyên tố cùng nhau.
Bài toán quy thành : tìm 2 số a, b nguyên tố cùng nhau sao cho a + b = N và abs(a – b) là nhỏ nhất ( để a * b là lớn nhất )
Bài tương tự:
https://codeforces.com/contest/1372/problem/B?fbclid=IwAR3cVhbFMzTF-C0x5x60XbgWrdk6OeiYGwLQJY5ruYCJV4_hb6cIusLbHss
