Số Lặp Lại (CPP0181)

Nguồn: Code PTIT (CPP0181) Độ khó: Dễ Ước chung lớn nhất Tìm quy luật Nhận xét

Đề bài

SỐ LẶP LẠI

Cho ba số $a$, $x$, $y$. Nhiệm vụ của bạn là tìm ước số chung lớn nhất của hai số $P$ và $Q$, trong đó $P$ lặp lại $x$ lần số $a$ và $Q$ lặp lại $y$ lần số $a$. Ví dụ $a = 2$, $x = 3$, $y = 2$ thì $P = 222$, $Q = 22$.

Input:

• Dòng đầu tiên đưa vào $T$ là số lượng bộ test.
• $T$ dòng tiếp theo đưa các bộ test. Mỗi bộ test được viết trên một dòng là bộ ba số $a$, $x$, $y$ phân biệt nhau bởi một vài khoảng trống.
• Các số $T$, $a$, $x$, $y$ thoả mãn ràng buộc: $1 \le T \le 100$; $1 \le a, x, y \le 10^{18}$.

Output:

• Đưa ra kết quả mỗi test theo từng dòng.

Giới hạn thời gian: 2s. Giới hạn bộ nhớ: 65536 Kb.

Input

2
2 2 3
123 5 2

Output

2
123

Lời mở đầu

Bài này là một bạn nhắn tin nhờ mình xem giúp code. Bạn ấy biết code mình bị lỗi do tràn dữ liệu nhưng chưa biết hướng giải quyết, sửa bằng chuỗi thì chưa nhuần nhuyễn nên thấy khó. Mình chia sẻ lại đoạn trao đổi thành bài giải này, vì cái hay của bài không nằm ở code (code chỉ vài dòng), mà nằm ở cách mình nhìn ra bản chất của bài toán. Các bạn thử sức tự làm trước rồi hãy đọc tiếp nhé 😉.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

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

Bài gốc nằm trên hệ thống Code PTIT (mã CPP0181), chỉ tài khoản sinh viên PTIT mới nộp được, nên mình đã đưa bài lên CLUE OJ ở trên để các bạn học viên nộp thử. Các bạn có thể chạy thử code ở trang Chạy code online của blog với các test ví dụ.

Giải thích ví dụ:

• Test 1: $a = 2$, $x = 2$, $y = 3$ ⇒ $P = 22$, $Q = 222$. $\gcd(22, 222) = 2$ (vì $22 = 2 \cdot 11$, $222 = 2 \cdot 3 \cdot 37$) ⇒ in 2.
• Test 2: $a = 123$, $x = 5$, $y = 2$ ⇒ $P = 123123123123123$, $Q = 123123$. $\gcd(P, Q) = 123$ ⇒ in 123.

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

Cách 1Lặp lại số a đúng gcd(x, y) lần · O(log + độ dài output)

Cách 1Số a lặp lại gcd(x, y) lần – O(log(min(x, y)) + độ dài kết quả)

Vì sao hướng "tạo ra số P, Q rồi tìm UCLN" không ổn?

Code của bạn học viên đi theo hướng rất tự nhiên: viết hàm tạo ra số lặp lại (nhân với $10^{\text{số chữ số của } a}$ rồi cộng $a$, lặp nhiều lần), sau đó tìm UCLN. Bạn ấy cũng đã nhìn ra đúng tư tưởng là có đi tìm UCLN của $x$, $y$. Nhưng sau đó, thay vì chỉ đơn giản là lặp lại in ra đủ bấy nhiêu lần số $a$, thì bạn lại đi xử lý để tạo ra một con số duy nhất rồi mới in, như thế rõ là không ổn:

Không thể tạo trực tiếp ra số đó

Giới hạn $x, y$ có thể tới $10^{18}$, vậy số $P$ có thể dài tới $10^{18}$ lần độ dài của $a$ chữ số! Kiểu số nguyên trong lập trình tối đa cũng cỡ 19, 20 chữ số thôi, nên chắc chắn không thể tạo trực tiếp ra số đó được, mà cũng không thể xử lý theo kiểu số lớn. Thêm nữa, (int)pow(10, num(a)) cũng tràn ngay khi $a$ có từ 10 chữ số trở lên.

Em nhìn vào đề bài tập, nó có nói rõ dạng bài nè: bài nằm trong nhóm "Lập trình C++ cơ bản", chủ đề con "Kiểu dữ liệu – Viết vòng lặp – Viết hàm". Có cái nào là xử lý chuỗi hay xử lý số lớn đâu ^^ nên rõ là mình đang suy nghĩ phức tạp rồi 🙂.

Bám theo ví dụ để tìm quy luật

Thực ra mình cũng chẳng đi tính công thức toán học chứng minh gì nhiều đâu, mình cứ bám theo ví dụ đề cho, như số $123$, rồi thử nghiệm:

• Lấy $123123123123123123$ (lặp lại 6 lần), thử chia cho $123$ lặp lại 1, 2, 3, 4, 5 lần.
• Tự nhiên nhìn ra: bản chất nó sẽ chia hết cho những số lần lặp mà 6 chia hết được. $6$ chia hết cho $1, 2, 3, 6$, vậy nghĩa là $123$ lặp lại $1, 2, 3, 6$ lần thì $123123123123123123$ (6 lần lặp lại) sẽ chia hết; còn lặp 4 lần, 5 lần thì không.
• Thử thêm vài số nữa, thấy quy luật đúng :))).

Từ đó ta sẽ nhìn ra rõ bản chất: cứ 2 số $x$, $y$ là số lần lặp lại, tìm ra ước chung lớn nhất của tụi nó, rồi sau đó cho số $a$ lặp lại nhiêu đó lần là xong!

Kết luận

$\gcd(\underbrace{aa\ldots a}_{x \text{ lần}},\ \underbrace{aa\ldots a}_{y \text{ lần}}) = \underbrace{aa\ldots a}_{\gcd(x, y) \text{ lần}}$. Kết quả chỉ cần in số $a$ ra $\gcd(x, y)$ lần liên tiếp, không cần tạo ra con số nào cả.

Chứng minh cho bạn nào tò mò

Gọi $R_k$ là số $a$ lặp lại $k$ lần và $B = 10^d$ với $d$ là số chữ số của $a$. Với $x \gt y$ thì $R_x$ chính là $R_y$ nối thêm $x - y$ khối $a$ phía sau: $R_x = R_y \cdot B^{x-y} + R_{x-y}$. Vì $R_y \cdot B^{x-y}$ chia hết cho $R_y$ nên $\gcd(R_x, R_y) = \gcd(R_{x-y}, R_y)$. Đây đúng y chang bước "lấy số lớn trừ số nhỏ" của thuật toán Euclid trên các số lần lặp $(x, y) \to (x - y, y)$. Euclid chạy tới khi hai số bằng nhau và bằng $\gcd(x, y)$ ⇒ đáp án là $R_{\gcd(x, y)}$. Khung minh hoạ dưới đây cho em thấy rõ từng bước này.

Minh hoạ

Em nhập $a$, $x$, $y$ rồi bấm Tiếp. Mỗi ô là một khối số $a$; mỗi bước ta "cắt" phần trùng với số nhỏ hơn ra khỏi số lớn hơn, UCLN không đổi:

a x y

Ví dụ nhanh:

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

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

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        long long a, x, y;
        cin >> a >> x >> y;

        long long res = __gcd(x, y);
        for(long long i = 1; i <= res; ++i)
            cout << a;

        cout << endl;
    }
    return 0;
}

from math import gcd

t = int(input())
for _ in range(t):
    a, x, y = map(int, input().split())
    res = gcd(x, y)
    print(str(a) * res)

C++▶ Chạy tay từng dòng codeTính gcd(x, y) rồi in số a đúng bấy nhiêu lần.

Dữ liệu vào (stdin) – sửa thoải mái2 2 2 3 123 5 2

Dữ liệu mẫu:

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

2using namespace std;

3

4int main()

5{

6 int t;

7 cin >> t;

8 while(t--)

9 {

10 long long a, x, y;

11 cin >> a >> x >> y;

12

13 long long res = __gcd(x, y);

14 for(long long i = 1; i <= res; ++i)

15 cout << a;

16

17 cout << endl;

18 }

19 return 0;

20}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: chỉ vài biến ⇒ $O(1)$.
• Thời gian: tìm UCLN bằng Euclid mất $O(\log(\min(x, y)))$, cộng với thời gian in kết quả $O(\gcd(x, y))$ lần in. Phần in là bắt buộc, vì đáp án dài chừng đó thì phải in chừng đó, không cách nào nhanh hơn được.

Không gian$O(1)$

Thời gian$O(\log \min(x, y) + \gcd(x, y))$

Một lời khuyên

Đó là hãy thử qua nhiều trường hợp input khác nhau, xem output có được gì, thì cứ thế sẽ nhận ra quy luật. Để rèn luyện tư duy cho thật tốt thì chỉ có nước là luyện tập nhiều vào thôi, làm nhiều bài lên nữa nhé 😉.

Đề cho x, y tới 10^18 thì in sao nổi?

Nếu $\gcd(x, y)$ thật sự cỡ $10^{18}$ thì đáp án có tới $10^{18}$ khối, không chương trình nào in nổi. Nên chắc chắn bộ test của đề có $\gcd(x, y)$ nhỏ (dù $x$, $y$ có thể rất lớn), và code trên đã AC trên hệ thống. Ý của giới hạn $10^{18}$ là để "chặn" hướng tạo ra số $P$, $Q$ thật sự.

Ghi chú của mình: code C++ và Python đã được kiểm tra với 300 bộ dữ liệu ngẫu nhiên ($x, y \le 60$, $a$ tới $10^{18}$), so với code vét cạn dựng thật hai số $P$, $Q$ bằng số nguyên lớn của Python rồi lấy UCLN – khớp hết. Với 100 bộ test $a, x, y$ cỡ $10^{18}$ và $\gcd(x, y) \le 1000$ (output hơn 3 triệu ký tự), cả hai bản đều chạy dưới 0.05 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 😇