Editorial for Bedao Mini Contest 12 - NUMGAME


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

Nhận xét: Vì ~4~ số ~a_1,a_2,b_1,b_2~ đôi một khác nhau nên số bộ số ~a_1,a_2,b_1,b_2~ sao cho ~a_1 \times a_2 > b_1 \times b_2~ bằng số bộ số ~a_1,a_2,b_1,b_2~ sao cho ~a_1 \times a_2 < b_1 \times b_2~.

Vì vậy, ta sử dụng bao hàm loại trừ bằng cách đếm số bộ số ~a_1,a_2,b_1,b_2~ sao cho ~a_1 \times a_ 2 = b_1 \times b_2~, sử dụng tổng số bộ ~4~ có thể, trừ đi và chia cho ~2~ sẽ là đáp án.

Ta có: ~a_1 \times a_2 = b_1 \times b_2~ ~\leftrightarrow~ ~\frac{a_1}{b_1} = \frac{b_2}{a_2}~

Đặt ~\frac{a_1}{b_1} = \frac{b_2}{a_2} = \frac{x}{y}~, với ~\frac{x}{y}~ là một phân số tối giản.

Bài toán: đếm số bộ ~a_1,a_2,b_1,b_2~ sao cho ~\frac{a_1}{b_1} = \frac{b_2}{a_2} = \frac{x}{y}~ và ~4~ số phân biệt nhau.

Ta thấy: ~\frac{x}{y}~ là phân số tối giản, khi và chỉ khi ~x~ và ~y~ nguyên tố cùng nhau. Có ~2~ trường hợp:

  • ~x < y~, thì số lượng số ~x~ sao cho ~\frac{x}{y}~ là phân số tối giản là ~phi(y)~. Với ~y~ xác định, ~y > x~ nên số phân số ~\frac{a}{b}~ sao cho ~a, b \leq N~ và ~\frac{a}{b} = \frac{x}{y}~ luôn xác định, vì vậy có thể đếm số bộ số trong ~O(1)~.
  • ~x > y~, thì số lượng số ~y~ sao cho ~\frac{x}{y}~ là phân số tối giản là ~phi(x)~. Với ~x~ xác định thì cũng sẽ tính được tương tự như trường hợp trên.

Nhưng như vậy thì sẽ có một trường hợp bị sai: Nếu ~\frac{a_1}{b_1} = \frac{b_2}{a_2}~ ~(1)~ thì sẽ có thể xảy ra trường hợp ~b_1 = b_2~, không thoả mãn điều kiện đề bài. Ta sẽ cần loại trừ số bộ ~4~ như vậy.

Sau đó, thế ~b_2 = b_1~ vào ~(1)~, ta có: ~\frac{a_1}{b_1} = \frac{b_1}{a_2}~ ~\leftrightarrow~ ~a_1 \times a_2 = {b_1}^2~

Lúc này ta sẽ có một bài toán như sau: Đếm số cặp số ~(a_1,a_2)~ sao cho tích ~a_1 \times a_2~ là số chính phương. Đây là bài khá cổ điển và có thể giải bằng sàng nguyên tố.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.