Mai (2023HITOPENDAY_4)

Nguồn: HAUI OJ – HIT Open Day 2023 Độ khó: Khá Số học Sàng Eratosthenes Phân tích thừa số nguyên tố Chẵn lẻ

Đề bài

MAI (mã bài 2023HITOPENDAY_4) – Input: standard input · Output: standard output · Giới hạn thời gian: 1 giây · Giới hạn bộ nhớ: 256 megabytes.

Chỉ còn bức tranh cuối cùng thôi, đó là "Mai". Cương đã tìm được chỗ bán bức tranh Mai đẹp nhất thế giới. Bức tranh đó có $n$ bông hoa mai.

Cơ mà tiền nào của nấy, vì đẹp nên bức tranh lại quá đắt, trong khi ngân quỹ còn có thể sử dụng là không nhiều. Cương quyết định mặc cả người bán hàng.

Người bán hàng đồng ý giảm giá bán của bức tranh xuống với một điều kiện, mỗi khi người bán hàng chỉ vào một bông hoa bất kì, Cương trả lời xem tích số cánh hoa của các bông hoa đã chỉ có phải số chính phương hay không.

Đơn thuần chỉ là tính toán thì không có gì, nhưng số lượng cánh hoa là khá lớn khiến máy tính cầm tay của Cương không thể tính nổi. Bạn hãy giúp Cương nhé.

Input:

• Dòng đầu tiên 1 số nguyên dương $n$ $(n \le 500000)$ — số lượng bông hoa mai.
• $N$ dòng tiếp theo, mỗi dòng một số nguyên dương $a$ $(a \le 10^6)$ – số cánh hoa của bông hoa được chỉ ở lượt tương ứng.

Output: $N$ dòng – tương ứng với $N$ lần trả lời. "YES" nếu tích số cánh hoa của các bông hoa đã chỉ là số chính phương. "NO" nếu ngược lại.

Subtask:

• Tích số cánh hoa của các bông hoa không vượt quá $10^{18}$: 30%.
• Mỗi bông hoa có số lượng cánh không quá 500: 40%.
• Không giới hạn gì thêm: 30%.

Ví dụ – standard input

7
2
3
6
15
35
21
64

Ví dụ – standard output

NO
NO
YES
NO
NO
YES
YES

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 toàn bộ hướng dẫn thành bài giải chi tiết để bạn nào chưa giải được thì có thể tham khảo nhen. Hy vọng mang đến được giá trị cho các bạn 😇.

Giải thích lại đề cho bạn nào chưa hiểu: người bán lần lượt chỉ vào $n$ bông hoa. Sau mỗi lần chỉ, ta nhân tất cả số cánh hoa của những bông đã được chỉ từ đầu tới giờ lại với nhau, rồi trả lời tích đó có phải số chính phương (bình phương của một số nguyên) hay không. Với ví dụ:

• Lượt 1: tích $= 2$ ⇒ không chính phương ⇒ NO.
• Lượt 2: tích $= 2 \cdot 3 = 6$ ⇒ NO.
• Lượt 3: tích $= 6 \cdot 6 = 36 = 6^2$ ⇒ YES.
• Lượt 4: tích $= 36 \cdot 15 = 540$ ⇒ NO.
• Lượt 5: tích $= 540 \cdot 35 = 18900$ ⇒ NO.
• Lượt 6: tích $= 18900 \cdot 21 = 396900 = 630^2$ ⇒ YES.
• Lượt 7: tích $= 396900 \cdot 64 = 25401600 = 5040^2$ ⇒ YES.

Chỉ mới 7 số nhỏ mà tích đã lên tới hơn 25 triệu rồi đó các bạn. Với $5 \cdot 10^5$ số, mỗi số tới $10^6$ thì tích sẽ có hàng triệu chữ số, nên ý định "nhân hết lại rồi kiểm tra" là không ổ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

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

Nhận xétSố mũ chẵn ⇔ chính phươngCách 1Phân tích O(√A) · TLECách 2Sàng ước nguyên tố nhỏ nhất · O(log A)

Nhận xét quan trọng: số mũ phải chẵn hết

Gợi ý đầu tiên mình đưa cho em học viên: một số là số chính phương thì khi phân tích số đó ra thừa số nguyên tố, các số mũ luôn là số chẵn. Các bạn nhìn thử nhé:

Số chính phương	Phân tích	Số chính phương	Phân tích
4	2^2	64	2^6
9	3^2	81	3^4
16	2^4	100	2^2 · 5^2
25	5^2	121	11^2
36	2^2 · 3^2	144	2^4 · 3^2
49	7^2	196	2^2 · 7^2

Các bạn có thấy số mũ trong các lũy thừa luôn là số chẵn không? Điều ngược lại cũng đúng: nếu mọi số mũ đều chẵn thì $X = p_1^{2k_1} p_2^{2k_2} \cdots = \left(p_1^{k_1} p_2^{k_2} \cdots\right)^2$ là số chính phương.

Ý chính

Tích là số chính phương $\iff$ trong phân tích thừa số nguyên tố của tích, không có số nguyên tố nào mang số mũ lẻ. Mà số mũ của $p$ trong tích chính là tổng số mũ của $p$ trong từng số đã đọc. Vậy ta không cần nhân gì cả, chỉ cần theo dõi tính chẵn lẻ của số mũ từng số nguyên tố!

Vì vậy mình xử lý từng số: mỗi số đọc từ input vào là đi phân tích thừa số nguyên tố, rồi kết hợp với các số trước đó để kết luận ở hiện tại là YES hay NO. Nhìn lại ví dụ mẫu:

• Đầu tiên là số $2$, phân tích được $2^1$ ⇒ $1$ là số lẻ ⇒ NO.
• Tiếp đến là số $3$, phân tích được $3^1$, nhưng phải nhớ là lúc này nó tính cả kết quả các số trước đó, nên phải hiểu tích đang là $2^1 \cdot 3^1$ ⇒ có số mũ lẻ ⇒ NO.
• Tiếp đến đọc vào $6$, phân tích ra được $2^1 \cdot 3^1$, nhưng trước đó ta đã có $2^1$ và $3^1$, vậy nên ở hiện tại tính ra sẽ là $2^2 \cdot 3^2$, đều là số mũ chẵn, không còn số mũ lẻ nào ⇒ YES.

Cài đặt cụ thể: dùng mảng check[p] = true nếu số mũ hiện tại của $p$ đang lẻ, và biến cnt = số lượng số nguyên tố đang có số mũ lẻ. Mỗi lần gặp thừa số $p$ (gặp bao nhiêu lần đảo bấy nhiêu lần):

• Đảo check[p]. Nếu nó thành true (chẵn → lẻ) thì cnt++; nếu thành false (lẻ → chẵn) thì cnt--.
• Đọc xong một số thì chỉ cần nhìn cnt: cnt == 0 ⇒ YES, ngược lại ⇒ NO. Không phải duyệt lại cả mảng nên mỗi lần trả lời là $O(1)$.

Minh hoạ: theo dõi số mũ chẵn/lẻ

Em nhập dãy số cánh hoa rồi bấm Tiếp để xem mỗi thừa số nguyên tố làm "đảo" số mũ như thế nào. Ô đỏ là số nguyên tố đang có số mũ lẻ, ô xanh là đã chẵn trở lại.

Dãy a

Ví dụ nhanh:

Đừng nhân hết các số lại

Nếu đi theo tư duy nhân hết các số lại thì sẽ bị tràn số chắc luôn. Kể cả long long cũng chỉ chứa được tới khoảng $9 \cdot 10^{18}$, nên cách nhân trực tiếp rồi lấy căn chỉ cứu được subtask 1 (tích $\le 10^{18}$) thôi các bạn nhé.

Cách 1Phân tích thừa số nguyên tố kiểu cơ bản – O(N·√A)

Có nhận xét rồi thì việc còn lại chỉ là phân tích từng số ra thừa số nguyên tố. Cách cơ bản nhất mà các bạn đều biết: thử chia $x$ cho $i = 2, 3, 4, \ldots$ chừng nào $i \cdot i \le x$; chia được bao nhiêu lần thì đảo check[i] bấy nhiêu lần. Hết vòng lặp mà $x \gt 1$ thì phần còn lại chính là một số nguyên tố (lớn hơn $\sqrt{x}$ ban đầu), đảo thêm nó một lần.

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 check[1000001];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    int cnt = 0;
    while(t--){
        int x;
        cin >> x;
        for(int i = 2; i * i <= x; ++i){
            while(x % i == 0){
                check[i] = !check[i];
                if(check[i] == true){
                    cnt++;
                }
                else{
                    cnt--;
                }
                x /= i;
            }
        }
        if(x > 1){
            check[x] = !check[x];
            if(check[x] == true){
                cnt++;
            }
            else{
                cnt--;
            }
        }
        if(cnt == 0){
            cout << "YES\n";
        }
        else{
            cout << "NO\n";
        }
    }
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    t = int(data[0])
    check = [False] * 1000001
    cnt = 0
    out = []
    for k in range(1, t + 1):
        x = int(data[k])
        i = 2
        while i * i <= x:
            while x % i == 0:
                check[i] = not check[i]
                if check[i]:
                    cnt += 1
                else:
                    cnt -= 1
                x //= i
            i += 1
        if x > 1:
            check[x] = not check[x]
            if check[x]:
                cnt += 1
            else:
                cnt -= 1
        out.append("YES" if cnt == 0 else "NO")
    sys.stdout.write("\n".join(out) + "\n")

main()

C++▶ Chạy tay từng dòng codeCách 1: thử chia từ 2 tới √x, đảo check[p] và cập nhật cnt.

Dữ liệu vào (stdin) – sửa thoải mái7 2 3 6 15 35 21 64

Dữ liệu mẫu:

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

2using namespace std;

3

4bool check[1000001];

5

6int main(){

7 ios::sync_with_stdio(0);

8 cin.tie(0);

9 cout.tie(0);

10 int t;

11 cin >> t;

12 int cnt = 0;

13 while(t--){

14 int x;

15 cin >> x;

16 for(int i = 2; i * i <= x; ++i){

17 while(x % i == 0){

18 check[i] = !check[i];

19 if(check[i] == true){

20 cnt++;

21 }

22 else{

23 cnt--;

24 }

25 x /= i;

26 }

27 }

28 if(x > 1){

29 check[x] = !check[x];

30 if(check[x] == true){

31 cnt++;

32 }

33 else{

34 cnt--;

35 }

36 }

37 if(cnt == 0){

38 cout << "YES\n";

39 }

40 else{

41 cout << "NO\n";

42 }

43 }

44 return 0;

45}

ChậmVừaNhanhRất nhanh

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

• Không gian: mảng check kích thước $10^6 + 1$ ⇒ $O(A)$ với $A = 10^6$.
• Thời gian: mỗi số phân tích mất $O(\sqrt{A})$. Có tối đa $N = 5 \cdot 10^5$ số, mỗi số tới $10^6$ ⇒ $\sqrt{10^6} = 10^3$ ⇒ $5 \cdot 10^5 \cdot 10^3 = 5 \cdot 10^8$ phép tính, vượt quá $10^8$ nên chắc chắn 1 giây sẽ chạy không nổi.

Không gian$O(A)$

Thời gian$O(N \cdot \sqrt{A})$

TLE với test xấu

Test xấu nhất là toàn các số nguyên tố lớn gần $10^6$ (ví dụ $999983$): vòng thử chia phải chạy đủ khoảng $1000$ lần cho mỗi số. Cách này qua được subtask 2 (mỗi số $\le 500$) nhưng sẽ bị TLE ở subtask cuối.

Cách 2Sàng ước nguyên tố nhỏ nhất – O(A·log log A + N·log A)

Nếu chỉ có 1, 2 giá trị cần phân tích thừa số nguyên tố thì ta làm theo kiểu cơ bản nhất với độ phức tạp $O(\sqrt{X})$ là ổn. Nhưng ở đây ta có nhu cầu phân tích rất nhiều số, nếu cứ mỗi số lại phải đi phân tích từ đầu thì sẽ rất lâu. Vì thế ta cần kết hợp sàng nguyên tố vào, để phân tích một số ra thừa số nguyên tố giờ đây không còn là $O(\sqrt{X})$ mà chỉ là $O(\log X)$.

Sàng ước nguyên tố nhỏ nhất

Dùng sàng Eratosthenes, nhưng thay vì đánh dấu "là hợp số", ta lưu luôn minPrime[x] = ước nguyên tố nhỏ nhất của $x$. Khi đó phân tích $x$ chỉ là: lấy $y = $ minPrime[x], ghi nhận thừa số $y$, rồi $x \mathrel{/}= y$, lặp lại tới khi $x = 1$. Mỗi lần chia $x$ giảm ít nhất một nửa ⇒ tối đa khoảng $\log_2 10^6 \approx 20$ bước.

Cách dựng mảng minPrime:

• Duyệt $i$ từ $2$ khi $i \cdot i \le n$. Nếu minPrime[i] == 0 thì $i$ là số nguyên tố, ta đi qua các bội $j = i \cdot i, i \cdot i + i, \ldots$; bội nào chưa có ước nhỏ nhất thì gán minPrime[j] = i. Vì $i$ duyệt tăng dần nên số đầu tiên gán vào chính là ước nguyên tố nhỏ nhất.
• Sau sàng, những $i$ vẫn còn minPrime[i] == 0 là số nguyên tố ⇒ gán minPrime[i] = i.

Ví dụ $x = 60$: minPrime[60] = 2 ⇒ $x = 30$ ⇒ minPrime[30] = 2 ⇒ $x = 15$ ⇒ minPrime[15] = 3 ⇒ $x = 5$ ⇒ minPrime[5] = 5 ⇒ $x = 1$. Ta được $60 = 2 \cdot 2 \cdot 3 \cdot 5$, đúng 4 bước. Phần đảo chẵn/lẻ và đếm cnt giữ y nguyên như Cách 1. Các bạn muốn hiểu kỹ hơn về sàng thì xem thêm bài viết Lý thuyết số – phần 2 trên VNOI Wiki, chú ý kỹ bắt đầu từ phần Sàng Eratosthenes nhé.

Đây là code mình đã nộp AC, các bạn tham khảo nhé:

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n = 1000000;
    vector<int> minPrime(n + 1, 0);
    for (int i = 2; i * i <= n; ++i) {
        if (minPrime[i] == 0) { // i là số nguyên tố
            for (int j = i * i; j <= n; j += i) {
                if (minPrime[j] == 0) {
                    minPrime[j] = i;
                }
            }
        }
    }
    for (int i = 2; i <= n; ++i) {
        if (minPrime[i] == 0) {
            minPrime[i] = i;
        }
    }
    int t;
    cin >> t;
    bool check[1000001] = {false};
    int cnt = 0;
    while(t--){
        int x;
        cin >> x;
        while(x != 1){
            int y = minPrime[x];
            check[y] = !check[y];
            if(check[y] == true){
                cnt++;
            }
            else{
                cnt--;
            }
            x /= y;
        }
        if(cnt == 0){
            cout << "YES\n";
        }
        else{
            cout << "NO\n";
        }
    }
    return 0;
}

import sys

def main():
    n = 1000000
    minPrime = [0] * (n + 1)
    i = 2
    while i * i <= n:
        if minPrime[i] == 0:  # i là số nguyên tố
            for j in range(i * i, n + 1, i):
                if minPrime[j] == 0:
                    minPrime[j] = i
        i += 1
    for i in range(2, n + 1):
        if minPrime[i] == 0:
            minPrime[i] = i

    data = sys.stdin.buffer.read().split()
    t = int(data[0])
    check = [False] * (n + 1)
    cnt = 0
    out = []
    for k in range(1, t + 1):
        x = int(data[k])
        while x != 1:
            y = minPrime[x]
            check[y] = not check[y]
            if check[y]:
                cnt += 1
            else:
                cnt -= 1
            x //= y
        out.append("YES" if cnt == 0 else "NO")
    sys.stdout.write("\n".join(out) + "\n")

main()

C++▶ Chạy tay từng dòng codeCách 2: sàng minPrime một lần, mỗi số chỉ chia cho minPrime[x] tới khi x = 1.

Dữ liệu vào (stdin) – sửa thoải mái7 2 3 6 15 35 21 64

Dữ liệu mẫu:

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

2using namespace std;

3

4int main(){

5 ios::sync_with_stdio(0);

6 cin.tie(0);

7 cout.tie(0);

8 int n = 1000000;

9 vector<int> minPrime(n + 1, 0);

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

11 if (minPrime[i] == 0) { // i là số nguyên tố

12 for (int j = i * i; j <= n; j += i) {

13 if (minPrime[j] == 0) {

14 minPrime[j] = i;

15 }

16 }

17 }

18 }

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

20 if (minPrime[i] == 0) {

21 minPrime[i] = i;

22 }

23 }

24 int t;

25 cin >> t;

26 bool check[1000001] = {false};

27 int cnt = 0;

28 while(t--){

29 int x;

30 cin >> x;

31 while(x != 1){

32 int y = minPrime[x];

33 check[y] = !check[y];

34 if(check[y] == true){

35 cnt++;

36 }

37 else{

38 cnt--;

39 }

40 x /= y;

41 }

42 if(cnt == 0){

43 cout << "YES\n";

44 }

45 else{

46 cout << "NO\n";

47 }

48 }

49 return 0;

50}

ChậmVừaNhanhRất nhanh

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

• Không gian: hai mảng minPrime và check kích thước $10^6 + 1$ ⇒ $O(A)$.
• Thời gian: sàng mất $O(A \log \log A)$, làm một lần duy nhất. Mỗi số phân tích tối đa $\log_2 A \approx 20$ bước ⇒ $5 \cdot 10^5 \cdot 20 = 10^7$ phép tính, thỏa $\lt 10^8$ nên yên tâm chạy trong 1 giây.

Không gian$O(A)$

Thời gian$O(A \log \log A + N \log A)$

Mẹo nhỏ

Lời giải không hề cần biết số mũ cụ thể là bao nhiêu, chỉ cần biết chẵn hay lẻ. Gặp những bài "tích có là số chính phương không" các bạn nhớ ngay tới kiểu đảo bit chẵn/lẻ này nhé.

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với 400 bộ test ngẫu nhiên nhỏ (có số 1, số chính phương, số nguyên tố lớn như $999983$), so với code vét cạn nhân trực tiếp bằng số nguyên lớn rồi lấy căn – khớp hết. Với $N = 5 \cdot 10^5$ số toàn là số nguyên tố gần $10^6$: Cách 1 (C++) chạy khoảng 2.4 giây ⇒ TLE đúng như phân tích; Cách 2 (C++) chạy khoảng 0.05 giây, với $5 \cdot 10^5$ số ngẫu nhiên khoảng 0.3 giây (bản Python của Cách 2 khoảng 1 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 😇