Hình Vuông (tht21_tphcm_slc_square) (Tin học trẻ TPHCM 2021, vòng sơ loại, bảng C)

Nguồn: VNOJ – Tin học trẻ 2021 TPHCM Độ khó: Trung bình Số học Phân tích thừa số nguyên tố Vét cạn

Đề bài

Tin học trẻ 2021 TPHCM – Vòng Sơ Loại – Bảng C – Hình vuông

Đăng là một học sinh chăm học trong lớp nên hay xung phong lên bảng làm bài. Trong giờ học môn Toán, Đăng được yêu cầu giải bài toán sau: cho biết độ dài cạnh hình vuông, tìm diện tích hình vuông đó. Ở bên dưới, Nhật mải quan sát mà quên mất việc ghi lại đáp số, khi nhớ ra thì bảng đã bị xóa mất! Nhật chỉ nhớ một số thông tin về tính chia hết của diện tích hình vuông. Nhật muốn tìm lại độ dài cạnh hình vuông, trong các độ dài thỏa mãn, Nhật muốn tìm độ dài nhỏ nhất. Bạn hãy giúp Nhật nhé!

Yêu cầu: Cho ba số nguyên dương $A, B, C$, bạn hãy viết chương trình tìm $X$ nguyên dương nhỏ nhất sao cho $X^2$ chia hết cho $A$, $B$ và $C$.

Dữ liệu: Nhập từ bàn phím một dòng duy nhất chứa ba số nguyên $A, B$ và $C$ $(1 \le A, B, C \le 10^6)$.

Kết quả: In ra màn hình duy nhất một số nguyên là độ dài nhỏ nhất của cạnh hình vuông có diện tích chia hết cho $A, B$ và $C$.

Ràng buộc:

• $30\%$ số điểm của bài tương ứng với các test có $B = C = 1$.
• $40\%$ số điểm khác của bài tương ứng với các test có $C = 1$.

Giới hạn thời gian: 1 giây.

Ví dụ 1 – input

2 9 1

Ví dụ 1 – output

6

Ví dụ 2 – input

16 1 1

Ví dụ 2 – output

4

Giải thích: Trong ví dụ đầu tiên, ta có $6^2 = 36$ chia hết cho 2, 9 và 1, và đây là giá trị nhỏ nhất thỏa mãn. Chú ý rằng $A, B, C$ có thể bằng nhau, như trong ví dụ thứ hai.

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.

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

Cái đề khúc đầu dông dài quá các bạn nhỉ 😅, thật ra đề chỉ nên từ phần yêu cầu trở đi cho gọn: cho 3 số nguyên dương $A, B, C$, tìm số nguyên dương $X$ nhỏ nhất sao cho $X^2$ chia hết cho cả $A$, $B$, $C$. (Trong bài này ký hiệu ^ là phép lũy thừa chứ không phải phép xor bit nha các bạn.)

Giải thích thêm ví dụ: với $A = 2, B = 9, C = 1$ ta thử lần lượt $X = 1, 2, 3, 4, 5$ thì $X^2 = 1, 4, 9, 16, 25$ đều không chia hết đồng thời cho 2 và 9; đến $X = 6$ thì $36$ chia hết cho cả 2, 9, 1 ⇒ đáp án 6. Với $A = 16$: $X = 4$ cho $16$ chia hết cho 16 ⇒ đáp án 4.

Nhắc lại ngưỡng TLE

Với giới hạn 1 giây, tổng số lần lặp của cả bài chỉ nên ở mức $(3 \div 5) \cdot 10^7$ là an toàn với phần lớn hệ thống chấm, cao lắm là $10^8$ (hên xui). Đó là với C/C++; Python, C#, Java chạy chậm hơn nên ngưỡng phải thấp hơn.

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

Cách 1Vét cạn X từ 1 trở lên · TLECách 2Phân tích thừa số nguyên tố · O(√A + √B + √C)

Cách 1Vét cạn X từ 1 trở lên

Đọc đề xong, cách làm đơn giản nhất mà nhiều bạn sẽ nhìn ra là vét cạn xét tất cả các số nguyên dương $X$ từ nhỏ nhất, tức là từ $1$ trở lên, cứ kiểm tra $X^2$ khi nào thấy chia hết cho cả 3 số $A, B, C$ thì $X$ đó chính là đáp án – vì ta đang đi từ nhỏ đến lớn nên đó là số nhỏ nhất thỏa mãn.

Số nguyên dương bắt đầu từ 1

Lưu ý số nguyên dương là tính từ $1$ trở lên chứ không phải từ $0$ nhé. $0$ chỉ là số nguyên, không âm cũng không dương. Nếu tính từ $0$ thì $0^2 = 0$ luôn chia hết cho mọi số, đáp án lúc nào cũng là $0$ – nhưng không phải như vậy hê hê.

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

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

int main(){
    int a, b, c;
    cin >> a >> b >> c;
    unsigned long long x = 0;
    while(++x){
        unsigned long long t = x * x;
        if(t % a == 0 && t % b == 0 && t % c == 0){
            break;
        }
    }
    cout << x;
    return 0;
}

a, b, c = map(int, input().split())
x = 0
while True:
    x += 1
    t = x * x
    if t % a == 0 and t % b == 0 and t % c == 0:
        break
print(x)

Rất ngắn gọn, rõ ràng, dễ hiểu đúng không các bạn? Để đề phòng số lớn bị tràn, mình chọn kiểu cho biến $X$ (và biến tạm $T$) là unsigned long long – số nguyên không dấu 8 byte, kiểu số nguyên có dung lượng lớn nhất trong C/C++, lưu được tới $18\,446\,744\,073\,709\,551\,615 \approx 1.8 \cdot 10^{19}$.

Cẩn thận với while(x++)

Lúc đầu mình viết x = 1; while(x++). Nhưng x++ là tăng sau: lần đầu kiểm tra điều kiện với giá trị 1 (đúng) rồi $x$ mới tăng thành 2, nên $X = 1$ không bao giờ được thử ⇒ test 1 1 1 sẽ in ra 2 thay vì 1. Code ở trên đã sửa lại thành x = 0; while(++x): tăng trước rồi mới kiểm tra, nên thử đúng từ $X = 1$.

C++▶ Chạy tay từng dòng codeCách 1: thử X = 1, 2, 3, ... đến khi X² chia hết cho cả a, b, c.

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

Dữ liệu mẫu:

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

2using namespace std;

3

4int main(){

5 int a, b, c;

6 cin >> a >> b >> c;

7 unsigned long long x = 0;

8 while(++x){

9 unsigned long long t = x * x;

10 if(t % a == 0 && t % b == 0 && t % c == 0){

11 break;

12 }

13 }

14 cout << x;

15 return 0;

16}

ChậmVừaNhanhRất nhanh

Tuy nhiên mọi thứ đâu đơn giản như vậy hê hê. Nộp thử lên web chấm thì sẽ bị TLE nha các bạn, chỉ được 14/20 test thôi, tới test 15 là bị TLE đứng lại.

Tại sao vậy? Giả sử $A, B, C$ là 3 số nguyên tố lớn nhất nhỏ hơn $10^6$: $999961$, $999979$, $999983$. Khi đó $X$ nhỏ nhất sao cho $X^2$ chia hết cho cả 3 số là $999\,923\,001\,838\,986\,077$ – tức vòng lặp while phải lặp gần $10^{18}$ lần! Trong khi với 1 giây tối đa chỉ cỡ $10^8$ lần lặp, vậy là cần cỡ $10^{10}$ giây ⇔ hơn 317 năm mới chạy ra kết quả, đến lúc đó chắc đã trải qua mấy đời con cháu rồi 😂.

Thậm chí nếu chờ được nhiêu đó thời gian thì cũng chẳng ra kết quả đúng: unsigned long long tối đa $18\,446\,744\,073\,709\,551\,615$, căn bậc hai của nó cỡ $4\,294\,967\,295.99$, nghĩa là chỉ cần $X$ vượt quá khoảng 4 tỷ 294 triệu thì $X^2$ đã bị tràn số và mọi kết quả sai từ đây. Muốn xử lý thì phải dùng số lớn (Python, Java, C# có hỗ trợ; C++ thì tự cài Big Int rất cực), vừa tốn công vừa chậm thêm. Nói chung có giải quyết được tràn số thì vẫn kẹt lại ở thời gian chạy.

• Subtask $B = C = 1$ (30%): đáp án không quá $A \le 10^6$ (vì $A^2$ luôn chia hết cho $A$) ⇒ chạy kịp.
• Subtask $C = 1$ và test tổng quát: đáp án có thể tới cỡ $10^{12}$ rồi $10^{18}$ ⇒ TLE. Mình thử bộ 999961 999979 1 (đáp án $\approx 10^{12}$) thì sau 10 giây chương trình vẫn chưa chạy xong.

Không gian$O(1)$

Thời gian$O(X)$ – $X$ là đáp án, có thể tới $\approx 10^{18}$

Vẫn nên cài đặt vét cạn

Thật ra ta có thể nhìn ngay từ đầu là cách này không ổn. Nhưng theo quan điểm của mình, nếu chưa nhìn ra cách tối ưu thì cứ cài vét cạn trước: nó luôn cho kết quả chính xác (với dữ liệu nhỏ) và cài rất nhanh, nên ta dùng nó làm công cụ kiểm tra cho cách tối ưu. Phần lớn các trang chấm không cho xem test sai, và trong các kỳ thi có tính penalty thì nộp sai nhiều lần còn bị tụt hạng, nên tự sinh test nhỏ so 2 code để tìm ra trường hợp sai là rất có ích.

Cách 2Phân tích thừa số nguyên tố – O(√A + √B + √C)

Bài này bản chất là bài số học. Mọi số nguyên dương đều phân tích được duy nhất thành tích các thừa số nguyên tố, ví dụ $72 = 2^3 \cdot 3^2$. Và chuyện chia hết nhìn qua thừa số nguyên tố rất rõ ràng:

• $M$ chia hết cho $A$ ⇔ với mỗi số nguyên tố $p$, số mũ của $p$ trong $M$ phải $\ge$ số mũ của $p$ trong $A$.
• Nếu $X = \prod p^{k_p}$ thì $X^2 = \prod p^{2k_p}$: bình phương lên thì mọi số mũ nhân đôi.

Gọi $e_p$ là số mũ lớn nhất của $p$ trong 3 số $A, B, C$ (đây cũng chính là số mũ của $p$ trong $\text{BCNN}(A, B, C)$). $X^2$ chia hết cho cả $A, B, C$ ⇔ với mọi $p$: $2k_p \ge e_p$ ⇔ $k_p \ge \lceil e_p / 2 \rceil$. Muốn $X$ nhỏ nhất thì lấy $k_p$ vừa đủ, không dư thừa số nguyên tố nào khác:

Công thức

$X = \prod\limits_{p} p^{\lceil e_p / 2 \rceil}$, với $e_p = \max\big(\text{mũ của } p \text{ trong } A,\ \text{trong } B,\ \text{trong } C\big)$.
Trong code: $\lceil e / 2 \rceil$ = (e + 1) / 2 (chia nguyên).

Thử với ví dụ 1: $A = 2 = 2^1$, $B = 9 = 3^2$, $C = 1$. Ta có $e_2 = 1 \Rightarrow k_2 = 1$; $e_3 = 2 \Rightarrow k_3 = 1$. Vậy $X = 2^1 \cdot 3^1 = 6$ ✔. Ví dụ 2: $16 = 2^4 \Rightarrow k_2 = 2$, $X = 2^2 = 4$ ✔. Còn 3 số nguyên tố lớn ở trên thì mỗi số có mũ 1 ⇒ $k = 1$ ⇒ $X = 999961 \cdot 999979 \cdot 999983 = 999\,923\,001\,838\,986\,077$, tính ra ngay lập tức 😍.

Phân tích một số $n \le 10^6$ ra thừa số nguyên tố thì dùng cách chia thử quen thuộc: thử chia $n$ cho $i = 2, 3, 4, \ldots$ chừng nào $i \cdot i \le n$, chia được bao nhiêu lần thì đó là số mũ của $i$; hết vòng lặp mà $n \gt 1$ thì phần còn lại chính là một số nguyên tố (mũ 1). Ta lưu số mũ lớn nhất của từng số nguyên tố vào một map tên cnt.

Minh hoạ

Em nhập $A, B, C$ rồi bấm Tiếp: lần lượt phân tích từng số, ghi số mũ vào bảng, hàng max là $e_p$, hàng cuối là $\lceil e_p/2 \rceil$ – số mũ của $p$ trong $X$.

A B C

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;

map<int, int> cnt;

void phanTich(int n){
    for(int i = 2; i * i <= n; ++i){
        int dem = 0;
        while(n % i == 0){
            n /= i;
            dem++;
        }
        if(dem > 0) cnt[i] = max(cnt[i], dem);
    }
    if(n > 1) cnt[n] = max(cnt[n], 1);
}

int main(){
    int a, b, c;
    cin >> a >> b >> c;
    phanTich(a);
    phanTich(b);
    phanTich(c);
    long long x = 1;
    for(auto p : cnt){
        int k = (p.second + 1) / 2;
        for(int j = 1; j <= k; ++j){
            x *= p.first;
        }
    }
    cout << x;
    return 0;
}

cnt = {}


def phan_tich(n):
    i = 2
    while i * i <= n:
        dem = 0
        while n % i == 0:
            n //= i
            dem += 1
        if dem > 0:
            cnt[i] = max(cnt.get(i, 0), dem)
        i += 1
    if n > 1:
        cnt[n] = max(cnt.get(n, 0), 1)


a, b, c = map(int, input().split())
phan_tich(a)
phan_tich(b)
phan_tich(c)
x = 1
for p, e in cnt.items():
    x *= p ** ((e + 1) // 2)
print(x)

Giải thích một số chỗ trong code:

1. Hàm phanTich(n): chia thử $n$ cho $i$ từ 2 trở đi chừng nào $i \cdot i \le n$. Mỗi lần chia hết thì n /= i và tăng dem. Vì ta chia "hết sạch" các thừa số nhỏ trước, nên mỗi khi dem > 0 thì $i$ chắc chắn là số nguyên tố. Hết vòng lặp mà n > 1 thì $n$ còn lại là một số nguyên tố lớn (mũ 1).
2. cnt[p] = max(cnt[p], dem): giữ số mũ lớn nhất của $p$ qua cả 3 số $A, B, C$ – chính là $e_p$.
3. k = (p.second + 1) / 2 là $\lceil e_p / 2 \rceil$, rồi nhân $p$ vào x đúng $k$ lần.
4. x kiểu long long: vì $\lceil e/2 \rceil \le e$ nên $X$ là ước của $\text{BCNN}(A, B, C) \le A \cdot B \cdot C \le 10^{18}$, vừa trong long long (khoảng $9.2 \cdot 10^{18}$), không cần số lớn gì cả.

C++▶ Chạy tay từng dòng codeCách 2: phân tích A, B, C ra thừa số nguyên tố, giữ mũ lớn nhất, rồi X = tích p^((e+1)/2).

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

Dữ liệu mẫu:

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

2using namespace std;

3

4map<int, int> cnt;

5

6void phanTich(int n){

7 for(int i = 2; i * i <= n; ++i){

8 int dem = 0;

9 while(n % i == 0){

10 n /= i;

11 dem++;

12 }

13 if(dem > 0) cnt[i] = max(cnt[i], dem);

14 }

15 if(n > 1) cnt[n] = max(cnt[n], 1);

16}

17

18int main(){

19 int a, b, c;

20 cin >> a >> b >> c;

21 phanTich(a);

22 phanTich(b);

23 phanTich(c);

24 long long x = 1;

25 for(auto p : cnt){

26 int k = (p.second + 1) / 2;

27 for(int j = 1; j <= k; ++j){

28 x *= p.first;

29 }

30 }

31 cout << x;

32 return 0;

33}

ChậmVừaNhanhRất nhanh

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

• Không gian: số lượng số nguyên tố khác nhau trong $A, B, C$ rất ít (mỗi số $\le 10^6$ có không quá 7 thừa số nguyên tố khác nhau) ⇒ coi như $O(1)$.
• Thời gian: chia thử mỗi số tốn tối đa $\sqrt{10^6} = 1000$ lần lặp ⇒ $O(\sqrt{A} + \sqrt{B} + \sqrt{C})$, tổng cộng chỉ khoảng 3000 lần lặp. So với gần $10^{18}$ lần của cách 1 thì đúng là một trời một vực 😍.

Không gian$O(1)$

Thời gian$O(\sqrt{A} + \sqrt{B} + \sqrt{C})$

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với 500 bộ test nhỏ ngẫu nhiên ($A, B, C \le 100$, có cả các số bằng 1), so với code vét cạn – khớp hết (code gốc x = 1; while(x++) sai ở bộ 1 1 1 nên mình đã sửa như trong hộp lưu ý ở cách 1). Cách 2 còn được kiểm tra thêm với 1500 bộ ngẫu nhiên $A, B, C \le 10^6$: đáp án luôn có $X^2$ chia hết cho $\text{BCNN}(A, B, C)$ và bỏ bớt bất kỳ thừa số nguyên tố nào thì không còn chia hết nữa. Với 999961 999979 999983 cách 2 chạy tức thì (C++ dưới 0.01 giây, Python khoảng 0.02 giây), còn cách 1 chỉ với 999961 999979 1 đã chạy quá 10 giây ⇒ TLE đúng như phân tích.

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 😇