trang chủ / đề bài / magicnum

Số ma thuật

Đề bài

Mô tả

Một số nguyên dương x được gọi là số ma thuật đối với cơ số b nếu khi biểu diễn x trong cơ số b (không có chữ số 0 ở đầu), mọi chữ số từ 0 đến b−1 đều xuất hiện một số chẵn lần (bao gồm cả 0 lần).

Cho q truy vấn, mỗi truy vấn gồm ba số b, l, r. Với mỗi truy vấn, hãy đếm số lượng số ma thuật đối với cơ số b nằm trong đoạn [l,r].

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên q — số truy vấn.
  • q dòng tiếp theo, mỗi dòng chứa ba số nguyên b, l, r.

Dữ liệu ra

In ra q dòng, mỗi dòng là đáp án của truy vấn tương ứng.

Ràng buộc

  • 1≤q≤105
  • 2≤b≤10
  • 1≤l≤r≤1018

Ví dụ

Input Output Giải thích
2
2 4 9
3 1 10		 1
2		 Truy vấn 1 (b=2): biểu diễn nhị phân của 4,5,…,9 lần lượt là 100,101,110,111,1000,1001. Chỉ có 9=10012 có số chữ số 0 và 1 đều chẵn. Truy vấn 2 (b=3): trong [1,10] chỉ có 4=113 và 8=223 là số ma thuật (cả ba chữ số 0,1,2 đều xuất hiện một số lần chẵn).
2
2 1 100
5 1 100		 21
4		 Trong [1,100] có 21 số ma thuật ở cơ số 2 và 4 số ma thuật ở cơ số 5.

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