Số thứ n
Xem PDF
Điểm:
400 (p)
Thời gian:
3.0s
Bộ nhớ:
1023M
Input:
bàn phím
Output:
màn hình
Bạn được cho 2 số nguyên dương \(a\) và \(b\).
Viết chương trình tìm số thứ \(n\) chia hết cho \(a\) hoặc \(b\).
Input
- Dòng đâu tiên chứa số nguyên dương \(T\) \((T \leq 10^5)\) - là số câu hỏi.
- \(T\) dòng, mỗi dòng chứa 3 số nguyên dương \(a, b, n\) \((a,b \leq 10^4, N \leq 10^9)\).
Output
- Gồm \(T\) dòng, mỗi dòng chứa câu trả lời cho mỗi câu hỏi.
Example
Test 1
Input
1
2 3 10Output
15Note
Giải thích Những số chia hết cho \(2\) hoặc cho \(3\) là \(2, 3, 4, 6, 8, 9, 10, 12, 14, 15, ....\)
Bình luận
Yêu cầu ad giảm mức nặng của test xuống cho python.
Để giải quyết bài toán này, ta có thể sử dụng phép toán LCM (Least Common Multiple - Bội số chung nhỏ nhất) và phép toán GCD (Greatest Common Divisor - Ước số chung lớn nhất).
Đầu tiên, chúng ta tính bội số chung nhỏ nhất (LCM) của a và b bằng cách sử dụng công thức: LCM(a, b) = a * b / GCD(a, b), trong đó GCD(a, b) là ước số chung lớn nhất của a và b.
Tiếp theo, chúng ta tính số lượng số chia hết cho a hoặc b trong đoạn từ 1 đến n bằng cách sử dụng công thức: count = n // a + n // b - n // LCM.
Sau đó, chúng ta tính số thứ n chia hết cho a hoặc b bằng cách sử dụng công thức: result = (n // a) * a + max(0, (n // b - n // LCM)) * b. Nếu count < n, ta cộng thêm max(0, (n - count - 1)) * LCM để tìm ra số thứ n chia hết cho a hoặc b.