TLEoj Contest #01 - Tổng chữ số cân bằng
Xem PDF
Nộp bài
Điểm:
2200 (thành phần)
Thời gian:
1.5s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Tác giả:
Dạng bài
Bạn được cho 2 số l,r. Ta gọi f(x) là tổng chữ số của x. Đếm số lượng số x nằm trong đoạn [l,r] thỏa mãn f(x)=f(x+f(x))
Input, Output và Subtasks
Input
- Dòng đầu tiên nhập số t chỉ số trường hợp thử nghiệm (t\le 3\cdot 10^5)
- Sau đó là t dòng, mỗi dòng nhập 2 số l,r (1\le l\le r\le 10^{18})
Output
- Với mỗi trường hợp thử nghiệm, xuất ra duy nhất 1 số trên một dòng là số lượng số x thỏa mãn
Subtasks
- Subtask 1 (5\%): 1\le l\le r\le 100.
- Subtask 2 (5\%): 1\le l\le r\le 10^3.
- Subtask 3 (10\%): 1\le l\le r\le 10^5.
- Subtask 4 (10\%): 1\le l\le r\le 10^6.
- Subtask 5 (10\%): 1\le l\le r\le 10^7.
- Subtask 6 (10\%): 1\le l\le r\le 10^8.
- Subtask 7 (10\%): t=1,r-l\le 10^6.
- Subtask 8 (40\%): Không có ràng buộc gì thêm
Sample
Input
5
1 81
12 125
69 420
90 120
12345 54321
Output
9
10
28
2
2939
Note
- Trong trường hợp thử nghiệm thứ nhất, các số thỏa mãn là: 9,18,27,36,45,54,63,72,81
- Trong trường hợp thử nghiệm thứ hai, các số thỏa mãn là: 18,27,36,45,54,63,72,81,108,117
- Trong trường hợp thử nghiệm thứ bốn, các số thỏa mãn là: 108,117
Bình luận