Editorial for Bedao Mini Contest 07 - PUZZLE


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Subtask 1 : ~x = 1~

Dễ thấy mọi con đường đều có ~GCD = 1~ vì chúng luôn xuất phát ở ô ~(x, x)~ có giá trị bằng ~1~, tổng ~GCD~ trong trường hợp này chính là số con đường có thể đi từ ô ~(1, 1)~ tới ô ~(n, m)~.

Note: Tham khảo mục Hệ số nhị thức (Binomial Coefficients) của bài viết sau nếu bạn chưa biết cách tính số đường đi từ ô ~(1, 1)~ tới ô ~(n, m)~ tại: Số học 5 - Các kiến thức cơ bản về Tổ hợp (Combinatorics)

Subtask 2 : ~t \leq 5~

Một số corner case cần lưu ý:

  • Nếu ~n = 1~ và ~m = 1~, đáp án hiển nhiên là ~x \times x~.
  • Nếu ~1~ trong ~2~ chiều ~n~ hoặc ~m~ bằng ~1~, đáp án là ~x~.

(sử dụng thuật toán bên dưới cho 2 case này sẽ gây lỗi)

Nhận xét #1: Chọn ~1~ số nguyên dương ~d~ bất kỳ, tô mọi ô ~(i, j)~ có giá trị ~i \times j~ chia hết cho ~d~ bằng màu đen và những ô còn lại bằng màu trắng. Nếu ô ~(i, j)~ là ô đen nhưng ~i, j~ đều không chia hết cho ~d~ thì các ô chung cạnh với nó sẽ là ô trắng (Phản chứng : ~2~ giá trị cùng chia hết cho ~d~ thì chênh lệch giữa chúng phải chia hết cho ~d~, tức ~\neq~ ~i, j~), ta gọi các ô đen có đặc điểm như trên là bị cô lập.

hình

Nhận xét #2: Giả sử có ít nhất ~1~ con đường có ~GCD = d~ ~\rightarrow~ tồn tại con đường đi từ ô ~(x, x)~ tới ô ~(x+n-1, x+m-1)~ mà chỉ đi qua các ô đen ~\rightarrow~ hiển nhiên ô ~(x, x)~ và ~(x+n-1, x+m-1)~ là các ô đen không bị cô lập ~\rightarrow~ ~d~ là ước chung của ~x~ và ~x+n-1~ hoặc ~x~ và ~x+m-1~.

Nhận xét #3: Nếu ~2~ số nguyên dương ~a, b~ có ~1 \leq |a-b| ≤ 5 \times 10^5~ thì ~GCD(a, b) \leq 5 \times 10^5~ vì ~|a-b|~ luôn chia hết cho ~GCD(a, b)~. Thay ~a, b~ bằng ~x~ và ~x+n-1~ (hoặc ~x+m-1~) ~\rightarrow~ ~GCD~ của mọi con đường luôn bé hơn hoặc bằng ~5 \times 10^5~.

Với mỗi số nguyên dương ~d \in [1, 5 \times 10^5]~ cần tính xem bao nhiêu con đường có ~GCD = d~.

Gọi ~f(d)~ là số con đường gồm toàn ô đen nếu số được chọn là ~d~, ~g(d)~ là số con đường có ~GCD = d~, nếu ta tính được ~f(d)~ ~∀~ ~d \in [1, 5 \times 10^5]~ thì cũng sẽ tính được ~g(d)~ ~∀~ ~d \in [1, 5 \times 10^5]~ bằng thuật toán sau:

hình

Độ phức tạp của thuật toán trên là: ~O(\sum_{i=1}^{5 \times 10^5} \frac{5 \times 10^5}{i})~ tức ~O(5 \times 10^5 \times log_2(5 \times 10^5))~

Bài toán quay về tính ~f(d)~ ~∀~ ~d \in [1, 5 \times 10^5]:~

  • Nếu ~d~ không là ước chung của ~x~ và ~x+n-1~ (hoặc ~x+m-1~) thì ~f(d) = 0~.
  • Nếu ~d~ thỏa mãn, ta chỉ quan tâm các ô ~(i, j)~ đen sao cho ~i~ hoặc ~j~ chia hết cho ~d~ (mọi ô đen còn lại đều bị cô lập), dễ thấy chúng tạo thành hình dạng như sau :

hình

Có thể coi hình dạng đặc biệt này như một bảng ~2~ chiều mới, điều kiện từ mỗi ô được đi sang phải và xuống dưới vẫn giữ nguyên vì vậy ta có thể tính được ~f(d)~ bằng tổ hợp.

Subtask 3:

Nếu ~f(d) = 0~ thì có thể bỏ qua vì chúng không làm ảnh hưởng đến kết quả, vậy ta sẽ lọc ra các trước các số d là ước chung của của ~x~ và ~x+n-1~ (hoặc ~x+m-1~) rồi xếp lại theo thứ tự tự tăng dần.

Sử dụng thuật toán sau để tìm ra ~g(d)~ ~∀~ ~d \in [1, 5 \times 10^5]~ khi biết ~f(d)~ ~∀~ ~d \in [1, 5 \times 10^5]~ (ở đây ~d~ là mảng chứa ước chung đã được lọc ra trong bước trước và ~s~ là kích cỡ của mảng ~d~ tính từ vị trí ~1~):

hình

Độ phức tạp của thuật toán trên là: ~O(s^2)~ với mỗi test case, trong thực tế ~s~ lớn nhất chỉ lên tới ~336~ và thuật toán ~O(t \times s^2)~ hoàn toàn đủ nhanh để qua giới hạn thời gian ~1.5s~


Comments

Please read the guidelines before commenting.


There are no comments at the moment.