Editorial for Bedao Regular Contest 09 - MNUMBER


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

Phân tích biểu thức từ đề bài, ta có: ~c = b^{2} - a^{2}~ ~\rightarrow~ ~c = (b - a) \times (b + a)~

Do đó, ~b - a~ sẽ là ước của ~c~ và ~b + a = \frac{c}{b - a}~.

Ta tiến hành duyệt qua tất cả ước ~u~ của ~c~ sao cho ~u * u \leq c~, với mỗi ước ~u~ như thế ~(u \leq \frac{c}{u}~ vì ~u \times u \leq c)~.

Nếu ~u = b - a~, ~\frac{c}{u} = b + a~. Ta có:

~a = \frac{(u - \frac{c}{u})}{2}~

~b = \frac{(u + \frac{c}{u})}{2}~

Nếu ~a~ và ~b~ nguyên thì đó là kết quả của đề bài (in ra YES cùng cặp số ~a~, ~b~), nếu không tìm được ~a~, ~b~ nguyên thì không tồn tại bất kì giá trị nào thỏa mãn (in ra NO)

Ngoài ra, ta có thể thử với nhiều số khác nhau và nhận thấy các số có tính chất sau đây:

  • Nếu ~C~ là số lẻ và ~C > 1~ đáp án thỏa mãn luôn là ~\frac{(C + 1)}{2}~ và ~\frac{(C + 1)}{2} - 1~.
  • Nếu ~C~ là số chẵn và ~C~ chia hết cho ~4~ thì kết quả là ~\frac{C}{4} + 1~ và ~\frac{C}{4} - 1~.

Riêng trường hợp ~n = 1~, chúng ta phải xét riêng vì đề bài yêu cầu rằng đáp án ~a~, ~b~ phải thuộc khoảng ~[1, 10^9]~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.