Editorial for Bedao Testing Contest 01 - FRAC


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: ntkwan

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

Please read the guidelines before commenting.


There are no comments at the moment.