trang chủ / đề bài / ht_ts10_26_b

Cặp ước chung

Đề bài

Mô tả

Ướ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≤x≤y≤n và có ước chung lớn nhất lớn hơn hoặc bằng k.

Dữ liệu vào

Một dòng duy nhất chứa hai số nguyên dương n,k (1≤k<n≤106), các số ghi cách nhau bởi một dấu cách.

Dữ liệu ra

Một số nguyên duy nhất là kết quả của bài toán.

Ràng buộc

  • 1≤k<n≤106.

Subtasks

  • Subtask 1 (70% số điểm): n≤103.
  • Subtask 2 (15% số điểm): n≤106, n−k≤103.
  • Subtask 3 (15% số điểm): Không có ràng buộc gì thêm.

Ví dụ

Input Output Giải thích
5 2 5 Các cặp số thỏa mãn là: (2,2),(2,4),(3,3),(4,4),(5,5).
10 3 13 (Ví dụ bổ sung.) Các cặp (x,x) với 3≤x≤10 (8 cặp) và (3,6),(3,9),(4,8),(5,10),(6,9).

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0