TLEoj Contest #11 - An interesting problem about digit sums
Xem PDF
Nộp bài
Điểm:
900 (thành phần)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Tác giả:
Dạng bài
Một bài toán rất thú vị về tổng chữ số
rất thích những tính chất thú vị về tổng chữ số nên cậu đã tự đặt bài toán cho mình như sau:
- Đầu tiên sẽ cho bạn 2 số l,r.
- Ta định nghĩa f(x)=|d(x)-d(x-1)|. Trong đó d(x) là tổng chữ số của x.
- Nhiệm vụ của bạn là hãy tính \sum_{i=l}^r f(i).
Input, Output và Subtasks
Input
- Dòng đầu tiên gồm một số nguyên dương t là số testcase (1\le t\le 2\times 10^4).
- Sau đó là t dòng, mỗi dòng gồm 2 số l,r\ (1\le l\le r\le 10^{18}).
Output
- Với mỗi testcase, in ra duy nhất 1 giá trị là kết quả của bài toán trên một dòng.
Scoring
- Subtask 1 (20\%): 1\le l\le r\le 10^7.
- Subtask 2 (80\%): Không giới hạn gì thêm.
Sample
Input
5
9 9
10 10
13 21
90 100
1 1000000000000000000
Output
1
8
16
34
1799999999999999999
Note
- Trong testcase thứ nhất, ta có f(9)=|d(9)-d(8)|=|9-8|=1.
- Trong testcase thứ hai, ta có f(10)=|d(10)-d(9)|=|1-9|=8.
- Trong testcase thứ tư, ta có:
- f(90)=|d(90)-d(89)|=|9-17|=8.
- f(91)=|d(91)-d(90)|=|10-9|=1.
- f(92)=|d(92)-d(91)|=|11-10|=1.
- f(93)=|d(93)-d(92)|=|12-11|=1.
- f(94)=|d(94)-d(93)|=|13-12|=1.
- f(95)=|d(95)-d(94)|=|14-13|=1.
- f(96)=|d(96)-d(95)|=|15-14|=1.
- f(97)=|d(97)-d(96)|=|16-15|=1.
- f(98)=|d(98)-d(97)|=|17-16|=1.
- f(99)=|d(99)-d(98)|=|18-17|=1.
- f(100)=|d(100)-d(99)|=|1-18|=17.
Tổng là: 8+1+1+1+1+1+1+1+1+1+17=34.
Bình luận