Hướng dẫn cho GCD - Tin hoc trẻ tỉnh Bắc Giang

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: letangphuquy

Đọc đề

Ý chính

Phần đầu cung cấp khá nhiều kiến thức thú vị, nhưng không cần thiết trong việc giải bài này. Chỉ cần đọc từ định nghĩa cách tính \(f\).

Subtask \(1\) (\(30\%\) số điểm): \(n,m \le 14, a,b \le 20\).

Tutorial

Nhận thấy tích \(A,B \le 20^{14} < 2\cdot 10^{18}\), chúng ta làm theo định nghĩa của đề bài: Dùng biến long long (số nguyên 64-bit) để tính \(A,B\), sau đó dùng hàm __gcd có sẵn của C++ hoặc tự code lại thuật toán Euclid.
Độ phức tạp: \(\mathcal{O}(m+n + \log(a^n + b^m))\) (\(\log\) tới từ độ phức tạp của thuật toán Euclid, trong trường hợp xấu nhất: Hai số được cho là hai số Fibonacci liên tiếp)

Solution
C++
long long A = 1, B = 1;
int n,m, a[], b[];
<Nhập vào n,m,a,b>
for (int i = 1; i <= n; i++) A *= 1ll * a[i]; // cần có 1ll * để tránh tràn số
for (int j = 1; j <= m; j++) B *= 1ll * b[j];
cout << __gcd(A,B);

Subtask \(2\) (\(30\%\) số điểm): \(n = 1\).

Tutorial

Hãy hình dung rằng: ta đang rút gọn phân số \(\frac{a_1}{b_1\cdot b_2\cdot b_3 \cdot \dots \cdot b_m}\).
Duyệt qua mảng \(b\), đặt \(g = \gcd(a_1, b_i)\) và dùng phép chia:

  • \(a_1 \leftarrow \frac{a_1}{g}\)
  • \(b_i \leftarrow \frac{b_i}{g}\)

Lấy giá trị lúc đầu của \(a_1\), đem chia cho giá trị \(a_1\) thu được sau cùng sau khi thực hiện các thao tác trên, ta có được ƯCLN
Độ phức tạp: \(\mathcal{O}(M + \log(a+b))\)

Subtask \(3\) (\(20\%\) số điểm): \(n,m,a,b \le 10^5\)

Tutorial

Phân tích mỗi số \(a,b\) ra thừa số nguyên tố (TSNT).
Ta chỉ quan tâm tới một số nguyên tố \(p\) bất kì. Để ý các tính chất:

  • \(p^a \cdot p^b = p^{a+b}\)
  • \(\gcd(p^a, p^b) = p^{\min(a,b)}\)

Từ những tính chất này, hoàn toàn mở rộng ra được các số tổng quát, bằng cách nhân kết quả tính \(\gcd\) của từng TSNT khác nhau lại. Lí do vì kết quả của mỗi TSNT hoàn toàn độc lập với những TSNT khác. Ví dụ, ta có:

  • \(\gcd(600, 180) = \gcd(2^3.3.5^2, 2^2.3^2.5) = \gcd(2^3,2^2) \gcd(3,3^2) \gcd(5^2,5) = 2^2 . 3 . 5 = 60\)
  • \(35.50 = 5.7 . 2.5^2 = 2^1 . 5^{2+1} . 7 = 1750\)

Với mỗi mảng \(a,b\), lưu tương ứng các mảng \(\texttt{deg_a, deg_b}\) có ý nghĩa như sau: \(\texttt{deg_a[x]}\) là bậc của TSNT \(x\) trong tích của \(n\) số thuộc dãy \(a\). Tương tự cho \(\texttt{deg_b[x]}\).
Để tính nhanh các lũy thừa \(p^{\texttt{min(deg_a[p], deg_b[p])}}\), sử dụng thuật toán chia để trị khá quen thuộc.
Độ phức tạp: \(\mathcal{O}((m+n)\sqrt(a+b) + (m+n)\log(m+n))\) (\(\log\) tới từ việc tính lũy thừa, còn \(\sqrt(a)\) tới từ việc phân tích TSNT)

Subtask \(4\) (\(20\%\) điểm): \(n,m \le 5\cdot 10^5, a,b \le 10^7\)

Tutorial

Subtask này chỉ đòi hỏi cải tiến thuật toán ở phần phân tích TSNT.
Có thể áp dụng một mẹo khá "phổ biến" hiện nay: Sàng nguyên tố. Ở đây thay vì lưu bool eratos[N] = true/false ứng với việc một số đã bị "gạch" khỏi sàng Eratosthenes hay chưa, ta lưu int div[N], với div[x] là giá trị của một ước số bất kì của \(x\).

C++
for (int i = 1; i <= MAX; i++) {
    if (div[i]) continue;
    for (int j = i; j <= MAX; j += i)
        div[j] = i; //j là bội của i
}

Ứng dụng div[x] để phân tích TSNT như sau:
C++
while (x > 1) {
    int p = div[x];
    ++deg[p];
    x /= p;
}

Độ phức tạp: \((m+n)\log(m+n))\)


Bình luận