Tính tổng (OLP2B)

Nguồn: LQDOJ (olp2b) – OLP MT&TN 2021 CT Độ khó: Khá Modulo Số học Số lớn

Đề bài

Tính tổng (OLP MT&TN 2021 CT)

Giới hạn thời gian: 2 giây. Giới hạn bộ nhớ: 512 MB (theo trang LQDOJ).

Trang https://lqdoj.edu.vn/ đang là một trang học lập trình của nhiều học sinh, đó cũng là trang mà Hồng luyện tập để chuẩn bị cho kỳ thi Tin học trẻ. Hàng ngày, mẹ giao nhiệm vụ dạy em Phúc luyện tập về phép cộng, để có nhiều thời gian code, Hồng đã nghĩ ra loại bài tập cho em Phúc như sau: Chọn một số nguyên dương $n$, em Phúc cần phải cộng liên tiếp các số $n$ cho tới khi tất cả các chữ số của tổng nhận được đều bằng nhau và trả lời số lượng số đã cộng. Ví dụ, nếu $n = 37$ thì em Phúc cần cộng ba số $37$ để nhận được tổng là $111$ có các chữ số giống nhau.

Nhằm lựa chọn số nguyên dương $n$ để em Phúc không phải cộng quá nhiều và kiểm tra câu trả lời của em Phúc, Hồng muốn xây dựng một chương trình tính số lượng số cần cộng với một số nguyên dương $n$.

Input:

• Vào từ thiết bị vào chuẩn gồm một dòng chứa một số nguyên dương $n$ $(n \lt 10^3)$.

Output:

• Ghi ra thiết bị ra chuẩn một dòng chứa một số nguyên là số lượng số cần cộng. Trường hợp số $n$ đã gồm các chữ số giống nhau chỉ cần ghi số 1, trường hợp không tồn tại tổng có các chữ số giống nhau ghi -1.

Scoring:

• Subtask 1 ($40\%$ số điểm): số lần cộng không vượt quá $10^6$;
• Subtask 2 ($60\%$ số điểm): không có ràng buộc nào thêm.

Ví dụ 1 – input

37

Ví dụ 1 – output

3

Ví dụ 2 – input

11

Ví dụ 2 – output

1

Ví dụ 3 – input

100

Ví dụ 3 – output

-1

Lời mở đầu

Bài này mình được một em học viên hỏi và mình đã hướng dẫn chi tiết cách thức giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình viết lại thành bài giải đầy đủ để các bạn tham khảo nhen. Hy vọng mang đến được giá trị cho các bạn 😇.

Giải thích ví dụ cho bạn nào chưa hiểu đề:

• $n = 37$: $37$ (chưa được), $37 + 37 = 74$ (chưa được), $37 + 37 + 37 = 111$ có các chữ số giống nhau ⇒ cộng 3 số.
• $n = 11$: bản thân $11$ đã có các chữ số giống nhau ⇒ in 1.
• $n = 100$: tổng luôn là $100, 200, 300, \ldots$, luôn tận cùng bằng $00$ mà chữ số đầu khác $0$ ⇒ không bao giờ được ⇒ in -1.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Cộng dồn từng lần · Subtask 1Cách 2Sinh số x + modulo + chia số lớn · 100%

Cách 1Làm theo đề: cộng dồn từng lần – Subtask 1

Khi mình hỏi em học viên có lấy được subtask 1 không, em trình bày: cho vào vòng for chạy $10^6$ lần, mỗi lần cộng thêm $n$ vào tổng rồi kiểm tra các chữ số có giống nhau không; hết $10^6$ lần mà vẫn chưa được thì in ra -1. Đúng là như vậy được với subtask 1, vì đề đã đảm bảo số lần cộng không vượt quá $10^6$.

Kiểm tra các chữ số giống nhau thì lấy chữ số cuối s % 10 làm mốc, rồi bóc dần từng chữ số (s % 10, s /= 10) xem có chữ số nào khác mốc không. Tổng lớn nhất khoảng $10^6 \cdot 999 \approx 10^9$ nên dùng long long cho chắc.

Source code để các bạn tham khảo nếu làm theo hướng này:

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

bool sameDigits(long long s){
    int last = s % 10;
    while(s > 0){
        if(s % 10 != last){
            return false;
        }
        s /= 10;
    }
    return true;
}

int main(){
    long long n, s = 0;
    cin >> n;
    for(int i = 1; i <= 1000000; ++i){
        s += n;
        if(sameDigits(s)){
            cout << i;
            return 0;
        }
    }
    cout << -1;
    return 0;
}

def sameDigits(s):
    last = s % 10
    while s > 0:
        if s % 10 != last:
            return False
        s //= 10
    return True

n = int(input())
s = 0
ans = -1
for i in range(1, 1000001):
    s += n
    if sameDigits(s):
        ans = i
        break
print(ans)

Đánh giá độ phức tạp của cách làm này: gọi $K$ là số lần cộng (tối đa $10^6$), mỗi lần kiểm tra chữ số mất khoảng 10 phép ⇒ $O(K \cdot \log_{10}(K \cdot n))$.

Không gian$O(1)$

Thời gian$O(K \cdot \log_{10}(K n))$

Chỉ lấy được subtask 1

Có những $n$ mà số lần cộng lớn khủng khiếp, ví dụ $n = 29$ cần cộng tới $38314176245210727969348659$ lần (tổng là số gồm 28 chữ số 1). Cách 1 sẽ dừng ở $10^6$ lần và in sai -1. Ngoài ra, mình có hỏi lại em: cũng subtask 1 thôi nhưng nếu time limit không phải 1–2 giây mà là 10 ms hay 5 ms thì sao? Cách lặp $10^6$ lần sẽ bị chạy quá thời gian. Cần nhìn ra cách tiết kiệm số lần lặp hơn, và chính nó sẽ là nền tảng cho cách làm tối ưu.

Cách 2Sinh số có các chữ số giống nhau + modulo + chia số lớn

Đổi góc nhìn: sinh ra kết quả trước

Đề bài cung cấp khá nhiều dữ kiện cho ta thấy hướng giải quyết, nhưng nếu chỉ nhìn đúng như đề mô tả thì ta sẽ đi cộng liên tiếp số $n$ đến khi nào ra kết quả. Hãy để ý: tổng sau cùng là một số có tất cả các chữ số bằng nhau, và tổng của $k$ số $n$ chính là $k \cdot n$.

Ý tưởng là tạo ra các số $x$ thoả mãn toàn bộ các chữ số giống nhau và thử xem $x$ có chia hết cho $n$ không. Nếu có thì đáp án là $x / n$. Đề cần số lần cộng ít nhất, tức $x / n$ nhỏ nhất, mà $n$ cố định ⇒ $x$ phải nhỏ nhất có thể. Vậy ta tạo các số $x$ theo giá trị tăng dần, gặp số $x$ đầu tiên chia hết cho $n$ thì tính $x / n$ ra đáp án và dừng luôn. Các giá trị $x$ tăng dần là:

12…91122…99111222…999111122223333…

Cứ thế đến vô tận… Nói vô tận cũng không đúng, vì đề nói nếu không có cách nào thì in ra -1. Mà làm sao biết được liệu có đáp án không? Theo tư duy của mình: thời gian có hạn nên cho lặp qua khoảng 1 triệu giá trị $x$ theo chiều tăng dần. Sau 1 triệu giá trị mà vẫn chưa tìm được $x$ chia hết cho $n$ thì kết luận luôn -1 😄, chứ sinh tiếp đến bao giờ.

1 triệu giá trị có đủ không?

Để chắc chắn, mình đã chạy thử với mọi $n$ từ $1$ đến $999$: trường hợp có đáp án thì $x$ dài nhất là $982$ chữ số (khi $n = 983$, $x$ gồm 982 chữ số 1), tức là chỉ cần chưa tới $9 \cdot 982 \approx 9\,000$ giá trị $x$. Còn các $n$ in -1 (ví dụ $10, 16, 20, 25, 100$…) thì là do phần thừa số 2 và 5 của $n$ (ví dụ $100 = 4 \cdot 25$, $16$, $10 = 2 \cdot 5$) không phải là $1, 2, 4, 5$ hay $8$: số gồm toàn chữ số 1 (11…1) luôn lẻ và không chia hết cho 5, nên số có các chữ số giống nhau chỉ "mượn" được thừa số 2, 5 từ chính chữ số $d \le 9$ mà thôi (mình đã kiểm tra quy luật này khớp với mọi $n \lt 1000$). Nên ngưỡng 1 triệu là dư dả.

Vấn đề: số $x$ quá lớn

Việc sinh ra số $x$ không khó, nhưng cần ngẫm chỗ này: kiểu số nguyên có sẵn lớn nhất 8 byte chỉ lưu được khoảng 19–20 chữ số. Trong khi đó mỗi độ dài có 9 số, nếu sinh 1 triệu số thì độ dài có thể lên tới $10^6 / 9 \approx 111\,111$ chữ số, làm gì có kiểu nào chứa nổi đúng không?

Hãy để ý: $x$ cực kỳ lớn nhưng $n$ rất nhỏ, chưa tới một ngàn. Kiểm tra $x$ chia hết cho $n$ tức là kiểm tra x % n == 0, nên ta chỉ cần biết $x \bmod n$ chứ không cần biết $x$. Ta dựa vào các tính chất modulo:

Tính chất modulo

$(a + b) \bmod c = ((a \bmod c) + (b \bmod c)) \bmod c$
$(a - b) \bmod c = ((a \bmod c) - (b \bmod c)) \bmod c$
$(a \cdot b) \bmod c = ((a \bmod c) \cdot (b \bmod c)) \bmod c$
Lưu ý là không có phép chia nhé, chỉ có cộng, trừ, nhân thôi.

Tưởng tượng khi $x = 11$ thì $11 = 1 \cdot 10 + 1$; khi $x = 555$ thì $555 = 55 \cdot 10 + 5$. Vậy với mỗi chữ số $d$, ta lưu trạng thái $a_d$ = (số gồm $L$ chữ số $d$) $\bmod n$. Giả sử đang ở $88$, khi sang $888$ chỉ cần lấy lại kết quả của $88$ đã $\bmod n$, nhân $10$, cộng $8$, rồi $\bmod n$:

Công thức cập nhật

$a_d \leftarrow (a_d \cdot 10 + d) \bmod n$. Khi nào $a_d = 0$ là đã tìm ra số $x$ bé nhất có toàn bộ chữ số bằng nhau và chia hết cho $n$.

Vì $a_d \lt n \lt 1000$ nên $a_d \cdot 10 + d$ chưa tới $10^4$, dùng int thoải mái.

Tính kết quả $x / n$

$x$ có thể là số rất lớn (vài trăm chữ số), nên:

• Code Python thì khoẻ, cứ tính trực tiếp x // n vì Python hỗ trợ số lớn sẵn. Các ngôn ngữ như C#, Java cũng có class BigInteger gọi ra xài thôi.
• Code C++ thì phải tự xử lý số lớn (big int) cho phép chia. Lúc làm bài mình đi copy nguyên source big int có sẵn về dùng 😄, còn nếu trong phòng thi thì phải tự ngồi code phép chia, y như phép chia hồi tiểu học á. Big int cũng phổ biến nên nhiều bạn còn học thuộc code luôn, để đụng là múc.

Ở bài này số chia $n$ nhỏ (dưới 1000) nên phép chia "số lớn cho số nhỏ" rất gọn: đi từ trái sang phải, hạ từng chữ số của $x$ xuống phần dư r = r * 10 + digit, ghi chữ số thương r / n (bỏ các số 0 ở đầu), rồi giữ lại dư r %= n. Trong code bên dưới mình viết luôn phần chia này thay cho cả thư viện big int để các bạn dễ đọc.

Minh hoạ sinh số và cập nhật số dư

Em nhập $n$ rồi bấm Tiếp: bảng có 9 dòng ứng với 9 chữ số $d$, cột cuối là $a_d = x \bmod n$. Dòng cam là số $x$ vừa sinh, dòng xanh là số $x$ chia hết cho $n$. (Khi số chữ số $L \ge 4$, mỗi bước gom cả 9 số cùng độ dài cho gọn.)

n

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

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

int main(){
    int n;
    cin >> n;
    int a[10] = {0};    // a[d] = (số gồm L chữ số d) % n
    int len = 0, digit = 0;
    // sinh tối đa 9 * 111111 (khoảng 1 triệu) số x tăng dần
    for(int L = 1; L <= 111111 && digit == 0; ++L){
        for(int d = 1; d <= 9; ++d){
            a[d] = (a[d] * 10 + d) % n;
            if(a[d] == 0){
                len = L;
                digit = d;
                break;
            }
        }
    }
    if(digit == 0){
        cout << -1;
        return 0;
    }
    // chia số lớn x (digit lặp len lần) cho n như phép chia tiểu học
    string q = "";
    int r = 0;
    for(int k = 0; k < len; ++k){
        r = r * 10 + digit;
        if(q != "" || r / n != 0){
            q += char('0' + r / n);
        }
        r %= n;
    }
    cout << q;
    return 0;
}

n = int(input())
a = [0] * 10        # a[d] = (số gồm L chữ số d) % n
length = 0
digit = 0
L = 1
# sinh tối đa 9 * 111111 (khoảng 1 triệu) số x tăng dần
while L <= 111111 and digit == 0:
    for d in range(1, 10):
        a[d] = (a[d] * 10 + d) % n
        if a[d] == 0:
            length = L
            digit = d
            break
    L += 1

if digit == 0:
    print(-1)
else:
    x = int(str(digit) * length)    # Python hỗ trợ số lớn sẵn
    print(x // n)

C++▶ Chạy tay từng dòng codeCập nhật a[d] = (a[d] * 10 + d) % n để tìm x nhỏ nhất, rồi chia số lớn x cho n.

Dữ liệu vào (stdin) – sửa thoải mái37

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main(){

5 int n;

6 cin >> n;

7 int a[10] = {0}; // a[d] = (số gồm L chữ số d) % n

8 int len = 0, digit = 0;

9 // sinh tối đa 9 * 111111 (khoảng 1 triệu) số x tăng dần

10 for(int L = 1; L <= 111111 && digit == 0; ++L){

11 for(int d = 1; d <= 9; ++d){

12 a[d] = (a[d] * 10 + d) % n;

13 if(a[d] == 0){

14 len = L;

15 digit = d;

16 break;

17 }

18 }

19 }

20 if(digit == 0){

21 cout << -1;

22 return 0;

23 }

24 // chia số lớn x (digit lặp len lần) cho n như phép chia tiểu học

25 string q = "";

26 int r = 0;

27 for(int k = 0; k < len; ++k){

28 r = r * 10 + digit;

29 if(q != "" || r / n != 0){

30 q += char('0' + r / n);

31 }

32 r %= n;

33 }

34 cout << q;

35 return 0;

36}

ChậmVừaNhanhRất nhanh

Một vài ghi chú về code:

• Vòng for ngoài sinh độ dài L, vòng trong sinh chữ số d từ 1 đến 9, nên các số $x$ được xét đúng theo thứ tự tăng dần $1, 2, \ldots, 9, 11, \ldots, 99, 111, \ldots$ Điều kiện digit == 0 ở vòng ngoài giúp dừng ngay khi đã tìm thấy.
• Với $L \le 111\,111$, ta xét tối đa $9 \cdot 111\,111 \approx 10^6$ số $x$, đúng như ngưỡng 1 triệu đã nói.
• Phép chia ở cuối bỏ qua chữ số 0 ở đầu thương: vì $x \ge n$ nên thương luôn có ít nhất một chữ số khác 0, q không bao giờ rỗng.
• Bản gốc của mình lúc nộp bài dùng nguyên một thư viện big int (cộng, trừ, nhân, chia đầy đủ) copy từ VNOI, phần của mình chỉ có hàm main với đúng ý tưởng trên. Ở đây mình thay thư viện đó bằng đoạn chia số lớn cho số nhỏ cho gọn, kết quả y hệt.
• Bản Python: int(str(digit) * length) dựng $x$ rồi lấy x // n. Python từ bản 3.11 giới hạn chuyển chuỗi thành số tối đa 4300 chữ số, ở bài này $x$ dài nhất chỉ 982 chữ số nên không sao.

Đánh giá độ phức tạp của cách làm này (gọi $L^*$ là độ dài của $x$ tìm được):

• Không gian: mảng 10 phần tử cộng chuỗi thương dài tối đa $L^*$ ⇒ $O(L^*)$.
• Thời gian: sinh số mất $O(9 \cdot L^*)$, chia số lớn mất $O(L^*)$. Với $n \lt 1000$ thì $L^* \le 982$, còn trường hợp -1 lặp đủ khoảng $10^6$ lần, vẫn rất nhanh.

Không gian$O(L^*)$

Thời gian$O(9 \cdot L^*)$, tối đa $\approx 10^6$

Ghi chú của mình: code C++ và Python ở trên cho đúng output 3 ví dụ của đề, và đã được kiểm tra với mọi $n$ từ $1$ đến $999$, so với một code vét cạn dùng số lớn thật của Python (thử lần lượt các số có chữ số giống nhau tăng dần, độ dài tới 3000) – khớp hết. Cách 1 cho kết quả đúng ở mọi $n$ có số lần cộng không vượt quá $10^6$ (đúng subtask 1) và in sai -1 ở các $n$ còn lại như $n = 29$. Trường hợp chạy lâu nhất (in -1, lặp đủ khoảng 1 triệu lần): C++ dưới 0.01 giây, Python khoảng 0.2 giây.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇