Editorial for Bedao Mini Contest 10 - HIDDEN


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ới ~LCM(LCM(x, y),a) = T~ thì ~x, y~ và ~a~ đều là ước của ~T~.
  • Với ~A~ là một ước của ~T~, ~LCM(T,A) = T~.

Nếu ~a~ thỏa mãn là ước của ~T~, ta quy về bài toán tìm ~x, y~ là ước của ~T~ sao cho ~LCM(x,y) = T~ và ~1 < x,y < T~.

Giả sử có cặp ~x, y~ thỏa mãn thì sau khi phân tích ~x, y~ và ~T~ ra các thừa số nguyên tố, sẽ có ít nhất một thừa số nguyên tố có bậc của ~x~ bằng bậc của ~T~, thừa số đó ở ~y~ sẽ có bậc bé hơn của ~T~ và cũng có ít nhất một thừa số nguyên tố có bậc ở ~y~ bằng ~T~, có bậc của ~x~ bé hơn.

Đơn giản hóa, ~T~ có dạng ~T = P^k \times T'~, với ~T'~ là 1 ước của ~T~, ~P~ là một số nguyên tố, ~k~ lớn nhất có thể và ~k > 0~.

Ta tìm và gán ~x = P^k~, ~y = T / x~. Nếu ~y = 1~ tức là ~T~ là lũy thừa của một số nguyên tố, khi đó không tồn tại thừa số nguyên tố thứ hai cấu tạo lên ~T~.

Trong trường hợp không tồn tại thừa số nguyên tố thứ hai cấu tạo lên ~T~ hoặc ~T~ không chia hết cho ~a~, ta chắc chắn không tìm được cặp ~x, y~ thỏa mãn và in ra ~-1~. Việc tìm ~P~ ở đây rất đơn giản vì ~P \le sqrt(T)~ hoặc ~P = T~ (nếu ~T~ là số nguyên tố).

Độ phức tạp: ~O(sqrt(T))~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.