Editorial for Bedao Testing Contest 01 - FRAC
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Gọi ~G~ là tích các số trong mảng ~a~.
Gọi ~F~ là bội chung nhỏ nhất các số trong mảng ~a~.
Do giá trị ~G~ trong mảng ~a~ có xu hướng tăng nhanh, nên nếu làm thuật toán duyệt để tính ~G~ và ~F~ rồi đem chia thì sẽ bị tràn số ( lớn hơn ~10^{18}~ ).
Thay vì đi tính ~G~ và ~F~ ta sẽ biểu diễn ~G~ và ~F~ dưới dạng thừa số nguyên tố ~X~ và số mũ ~xG~ và ~xF~. Với ~F~ thì thừa số nguyên tố ~X~ có trong ~F~ phải lấy số mũ ~max~ trong các số ~a_i~.
Quan sát phép tính ~\frac{G}{F}~, ta thấy với thừa số nguyên tố là ~X~ có số mũ ở ~G~ là ~xG~ và số mũ ở ~F~ là ~xF~, ~X~ sẽ xuất hiện cả ở trong ~G~ và ~F~ nên kết quả của ~\frac{G}{F}~ mà có thừa số nguyên tố ~X~ sẽ là ~X^{xG-xF}~. Vậy trong trường hợp tổng quát có ~k~ số ~X~ xuất hiện trong cả ~G~ và ~F~ thì đáp án bài toán là:
~X_1^{xG_1-xF_1} \times X_2^{xG_2-xF_2} \times X_3^{xG_3-xF_3} \times ... \times X_k^{xG_k-xF_k}~
Ta thấy sẽ không tồn tại ~xG - xF < 0~ vì với thừa số nguyên tố ~X~ thì ~xF = max(xG)~ cho nên ~xF \leq xG~.
Comments