Bài 2: Cặp ước chung (TS10 Hà Tĩnh 2026)

Xem PDF



Tác giả:
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Đ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\)\(b\) là số nguyên dương \(c\) lớn nhất mà cả \(a\)\(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

  • \(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\).
  • \(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.

Bình luận (1)

Mới nhất
Tải bình luận...

Kỳ thi: