Tổng bình phương chữ số
Đề bài
Tổng bình phương chữ số [DIGITSQR]
Cho số nguyên dương $x$. Lập dãy vô hạn $A = (a_1, a_2, \ldots)$ theo quy tắc:
- $a_1 = x$;
- $a_i$ bằng tổng bình phương các chữ số của $a_{i-1}$ với mọi $i > 1$.
Hãy xác định số lần xuất hiện của một số nguyên $v$ trong $n$ phần tử đầu tiên của dãy $A$.
Dữ liệu:
- Dòng đầu tiên chứa số nguyên $T$ $(1 \le T \le 30)$ là số tests.
- Tiếp theo là $T$ dòng, mỗi dòng gồm ba số nguyên $x, v, n$ $(1 \le x, v, n \le 10^9)$.
Kết quả: Dòng $1 \ldots T$: dòng $i$ ghi số nguyên kết quả của test $i$.
Giới hạn:
- 50% điểm đầu tiên với $n \le 10^5$;
- 50% điểm còn lại không có giới hạn gì thêm.
Giải thích ví dụ: với $x = 13$: dãy là $13, 10, 1, 1, 1, \ldots$ ($1^2 + 3^2 = 10$, $1^2 + 0^2 = 1$, $1^2 = 1$). Trong 10 phần tử đầu, số $1$ xuất hiện $8$ lần. Với $x = 4$: dãy là $4, 16, 37, 58, 89, 145, \ldots$ – trong 6 phần tử đầu không có số $8$.
2
13 1 10
4 8 68
0Lời mở đầu
Đọc đề thấy $n$ tới $10^9$, nếu sinh đủ $n$ phần tử thì chắc chắn chậm. Mấu chốt của bài là nhận ra dãy này rất nhanh rơi vào một vòng lặp (chu trình), và ta có thể dùng map để "nhớ" mỗi giá trị đã xuất hiện ở vị trí nào – gặp lại giá trị cũ là biết ngay chu trình bắt đầu ở đâu, dài bao nhiêu. Sau đó chỉ cần một phép chia là đếm xong.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
Bộ test có 100 test, test nào cũng có đủ $T = 30$ truy vấn:
| Test | Số truy vấn T | x lớn nhất | v lớn nhất | n lớn nhất | Đáp án = 0 | Đáp án lớn nhất |
|---|---|---|---|---|---|---|
| 1–30 | 30 | 99 | 99 | 30 | 0/900 | 30 |
| 31–50 | 30 | 970.087.179 | 288 | 99.798 | 0/600 | 96.543 |
| 51–70 | 30 | 931.038.318 | 493 | 9.813.090 | 0/600 | 9.813.090 |
| 71–100 | 30 | 987.349.099 | 560 | 1.000.000.000 | 0/900 | 1.000.000.000 |
Đối chiếu giới hạn của đề với test thật và số test đúng của từng cách:
| Phần | Đề ghi | Test | Thực tế | Cách 1 (mô phỏng) | Cách 2 (map + chu trình) |
|---|---|---|---|---|---|
| 50% đầu | $n \le 10^5$ | 1–50 | test 1–30: $x, n < 100$; test 31–50: $n < 10^5$ | 50/50 | 50/50 |
| 50% còn lại | không giới hạn thêm | 51–70 | $n \approx 10^7$ | 20/20 | 20/20 |
| 71–100 | $n$ tới $10^9$ | 0/30 | 30/30 |
Một con số thú vị mình đo được: trên toàn bộ 3000 truy vấn, dãy chỉ cần sinh tối đa 20 giá trị khác nhau là đã gặp lại một giá trị cũ. Đó là lý do cách 2 chạy gần như tức thì.
Ý tưởngDãy luôn rơi vào chu trình
Với $x \le 10^9$ thì $x$ có tối đa 10 chữ số, nên $a_2 \le 10 \cdot 9^2 = 810$. Từ đó trở đi mọi phần tử đều $\le 810$ (một số có 3 chữ số cho tổng bình phương không quá $3 \cdot 81 = 243$). Dãy chỉ nhận hữu hạn giá trị và mỗi phần tử chỉ phụ thuộc phần tử ngay trước nó, nên sớm muộn sẽ gặp lại một giá trị cũ – từ đó dãy lặp lại y hệt mãi mãi.
Ví dụ $x = 4$: $\underbrace{4 \to 16 \to 37 \to 58 \to 89 \to 145 \to 42 \to 20}_{\text{chu trình dài 8}} \to 4 \to \ldots$. Còn $x = 13$: $13 \to 10 \to \underbrace{1}_{\text{chu trình dài 1}} \to 1 \to \ldots$ ($13, 10$ là phần "đuôi" trước chu trình).
pos[giá trị] = vị trí đầu tiên trong một map. Khi sinh ra giá trị $a$ đã có trong map ở vị trí $j$: chu trình bắt đầu ở $st$ = pos[a], dài $c = j - st$. Nếu $v$ không có trong map thì đáp án 0. Ngược lại gọi $k$ = pos[v]:
- $k > n$: $v$ chưa kịp xuất hiện → 0.
- $k < st$: $v$ nằm ở phần đuôi, xuất hiện đúng 1 lần.
- $st \le k \le n$: $v$ xuất hiện ở các vị trí $k, k + c, k + 2c, \ldots \le n$ → $\lfloor (n - k) / c \rfloor + 1$ lần.
Em nhập $x, v, n$ rồi bấm Tiếp để xem dãy được sinh ra, map được điền dần và chu trình hiện ra:
Cách 1Mô phỏng đủ n phần tử – 50% điểm
Làm đúng như đề: sinh lần lượt $n$ phần tử, gặp $v$ thì đếm. Hàm f(x) tách từng chữ số bằng x % 10 và x /= 10.
Kết quả chạy thật: bản C++ đúng 70/100 test (quá thời gian ở test 71–100), test đúng chạy lâu nhất 0.88s; bản Python (chỉ chạy test 1–60) đúng 50/60 test (quá thời gian ở test 51–60), test đúng lâu nhất 0.49s. Ăn trọn 50% điểm đầu ($n \le 10^5$), và bất ngờ là còn "lì" qua được cả 20 test 51–70 ($n \approx 10^7$): 30 truy vấn là khoảng $3 \cdot 10^8$ lần gọi f, nhưng sau phần tử thứ hai các số đều nhỏ (tối đa 3 chữ số) nên mỗi lần gọi rất nhẹ – dù vậy nhiều test mất 0.6–0.9 giây, rất sát giới hạn. Với $n$ tới $10^9$ (test 71–100) thì không thể kịp.
Cách 2map nhớ vị trí, tìm chu trình – Full điểm
while (pos.find(a) == pos.end()): còn chưa gặp lại giá trị cũ thì ghi vị trí của $a$ rồi sinh tiếp. Vòng này chỉ chạy vài chục lần.- Khi thoát vòng, $a$ chính là giá trị bị lặp, $j$ là vị trí mà nó xuất hiện lần thứ hai, nên chu trình bắt đầu ở
st = pos[a]và dàic = j - st. - Mọi giá trị trong map đều khác nhau, nên $v$ (nếu có) chỉ có một vị trí đầu tiên $k$. Ba trường hợp đúng như phần ý tưởng.
- Kiểu
long longcho $n, k$ không bắt buộc ($\le 10^9$ vừaint), mình dùng cho an toàn.
Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng chạy lâu nhất 0.00s; bản Python đúng 100/100 test, test đúng lâu nhất 0.03s.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Test đúng lâu nhất | Ghi chú |
|---|---|---|---|---|
| 1. Mô phỏng $n$ phần tử | C++ | 70/100 | 0.88s | Quá thời gian test 71–100 |
| Python | 50/60 | 0.49s | Chỉ chạy test 1–60; quá thời gian test 51–60 | |
2. map tìm chu trình | C++ | 100/100 | 0.00s | Full điểm |
| Python | 100/100 | 0.03s | Full điểm (dict) |
map để phát hiện chu trình thì mỗi truy vấn chỉ sinh không quá 20 phần tử, chạy tức thì với cả C++ lẫn Python.
Nhận xét
Đăng nhận xét