Editorial for Bedao Mini Contest 10 - HIDDEN
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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