Đếm số (THTB Hòa Vang 2022)
Xem PDF
Điểm:
300
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho \(3\) số nguyên dương \(x, n, m\). Hãy đếm xem có bao nhiêu số nguyên dương \(y\) thỏa mãn:
- \(y\le n\)
- \(x \times y\) chia hết cho \(m\)
Yêu cầu: Cho trước \(x, n, m\), hãy lập trình tìm số lượng số \(y\) thỏa mãn.
Input
- Một dòng chứa \(3\) số \(x, n, m ( x, n, m\le 10^{16})\).
Output
- Một số nguyên là số lượng số nguyên \(y\) thỏa mãn yêu cầu của bài toán.
Scoring
- Subtask \(1\) (\(40\%\) số điểm): \(n \le 10^4\).
- Subtask \(2\) (\(30\%\) số điểm): \(n \le 10^8\).
- Subtask \(3\) (\(30\%\) số điểm): không có ràng buộc gì thêm.
Example
Test 1
Input
6 13 8Output
3Note
Giải thích: Có \(3\) giá trị y thỏa mãn là: \(4\); \(8\); \(12\)
Bình luận
Hint
ans=n/(LCM(x,m)/x)
Hàm LCM là hàm lấy bội chung nhỏ nhất của 2 số
|| Hint
Mình test cái hint này tí thôi các anh chị em đừng nói mình ạ :'(
Gọi lcm là bội chung nhỏ nhất của x và m
ta có kết quả là: res = n // (lcm // x)
||
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.