30/09/2018, 18:03
Bài toán giá trị chung nhỏ nhất của các cấp số nhân (Codeforces.com)
Chào cả nhà,
Trên Codeforces có bài toán về cấp số nhân có đề bài như bên dưới. Chỗ tìm ra kết quả -1 mình không biết làm thế nào, xin nhờ các bạn chỉ hướng đi.
Cấp số nhân là dãy số bao gồm a là số hạng đầu, b là công bội, dãy có dạng:a, ab, ab², ab³,…
Đề bài cho ta dãy các cấp số nhân. Cần tìm giá trị x thuộc trong tất cả các giá trị trong các cấp số nhân đã cho, và x là nhỏ nhất.
Input bao gồm:
- Dòng 1: giá trị n là số dãy cấp số nhân.
- Các dòng tiếp theo, mỗi dòng gồm 2 giá trị: số hạng đầu, công bội.
Output: giá trị x, nếu không tồn tại thì xuất -1.
Ví dụ:
Input:
2
2 2
4 1
Output:
4Input:
2
2 2
3 3
Output:
-1
Nguồn: http://codeforces.com/problemset/problem/571/E
Bài liên quan
Mình nghĩ là quy về bài toán tìm bội chung nhỏ nhất.
Kiểm tra xem ucln của các phần tử a*b giữa các chuỗi. Nếu là 1 thì có nghĩa là các dãy không có phần tử chung, return -1.
Nếu khác 1 thì tìm bcnn bằng công thức.
Duyệt và tính tuần tự là được.
Hi Hoàng,
Như thế không được đâu, vì đây là dãy số tăng theo cấp số nhân (tăng theo bội số), còn lấy bội chung nhỏ nhất là nó tăng theo cấp số bất kì rồi.