Cách đầu tiên để giải bài toán là đếm thủ công số lần chữ số ~1~ xuất hiện ở tất cả các số từ ~0~ đến ~n~, nhưng cách này rất chậm. Vì thế, ta cần tìm một quy luật về việc chữ số ~1~ xuất hiện ở các vị trí như hàng đơn vị, hàng chục, hàng trăm,… để từ đó tính ra kết quả nhanh hơn.

Ta nhận thấy rằng:

• Chữ số ~1~ ở hàng đơn vị sẽ xuất hiện đều đặn sau mỗi ~10~ số, ví dụ: ~1, 11, 21, ..., 121, ...~

• Chữ số ~1~ ở hàng chục sẽ xuất hiện đều sau mỗi ~100~ số, ví dụ: ~10–19, 110–119, 210–219,...~

• Tương tự, chữ số ~1~ ở hàng trăm sẽ lặp lại sau mỗi ~1000~ số,…

Dựa vào quy luật này, ta có thể tính nhanh số lần chữ ~1~ xuất hiện ở mỗi hàng.

Công thức tổng quát để tính là:

$$ \left\lfloor \frac{n}{10\times i} \right\rfloor \times i $$

Phần dư "chưa đủ một chu kỳ"

Sau khi lấy hết các chu kỳ đầy đủ, chúng ta còn thừa lại ~\,n \bmod (10i)~ số ở cuối, từ đầu chu kỳ đến số ~n~. Trong phần dư này, vị trí ~i~ có thể còn xuất hiện thêm một số lần ~1~.

Xét phần dư ~r = n \bmod (10i)~. Đó là đoạn còn lại ~r~ số sau khi đã lấy hết các chu kỳ đầy đủ.

1. Nếu ~r < i~: đoạn còn lại chỉ chạy qua các chỉ số ~0…r~, mà ~1~ chỉ bắt đầu từ chỉ số ~i~ ~\longrightarrow~ Không có lần ~1~ nào nữa, cộng ~0~.

2. Nếu ~i \le r < 2i~: đoạn còn lại chạy qua chỉ số ~i, i+1, ..., r~. Số chỉ số trong khoảng này là ~(r - i + 1)~ ~\longrightarrow~ Cộng thêm ~r - i + 1~ lần ~1~.

3. Nếu ~r \ge 2i~: đoạn còn lại ít nhất chạy hết cả khoảng ~i~ đến ~2i-1~ ~\longrightarrow~ Cộng trọn ~i~ lần ~1~.

Ta được công thức:

$$ \min\left(\max\left(n \bmod (10\times i) - i + 1,\ 0\right),\ i\right) $$

#include <bits/stdc++.h>
using namespace std;

void sol(){
    int n; cin >> n;
    int cnt = 0;
    for (long long i = 1; i <= n; i *= 10) {
        long long p = i * 10;
        cnt += (n / p) * i + min(max(n % p - i + 1, 0LL), i);
    }
    cout << cnt << "\n";
}

int main(){
    int t; cin >> t;
    while(t--) sol();
}