Bài 2: Cặp ước chung (TS10 Hà Tĩnh 2026)
Xem PDF
Điểm:
1600 (p)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Ước chung lớn nhất của hai số nguyên dương \(a\) và \(b\) là số nguyên dương \(c\) lớn nhất mà cả \(a\) và \(b\) đều chia hết cho nó.
Cho hai số nguyên dương \(n, k\).
Yêu cầu: Hãy đếm số lượng cặp số nguyên dương \(x, y\) thỏa mãn \(1 \leq x \leq y \leq n\) và có ước chung lớn nhất lớn hơn hoặc bằng \(k\).
Input
- Một dòng duy nhất chứa hai số nguyên dương \(n, k\) (\(1 \leq k < n \leq 10^6\)), các số ghi cách nhau bởi một dấu cách.
Output
- Một số nguyên duy nhất là kết quả của bài toán.
Example
Test 1
Input
5 2
Output
5
Note
Các cặp số thỏa mãn là: \((2, 2), (2, 4), (3, 3), (4, 4), (5, 5)\).
Scoring
- Có \(70\%\) số test ứng với \(70\%\) số điểm của bài thỏa mãn điều kiện: \(n \leq 10^3\).
- Có \(15\%\) số test ứng với \(15\%\) số điểm của bài thỏa mãn điều kiện: \(n \leq 10^6, n - k \leq 10^3\).
- \(15\%\) số test còn lại ứng với \(15\%\) số điểm không có ràng buộc gì thêm.
Kỳ thi:
- Tuyển sinh lớp 10 Chuyên tỉnh Hà Tĩnh 2026 (26 Tháng năm, 2026)
Bình luận (1)