trang chủ / bài tập / 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.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0