---
# System prepended metadata

title: Luỹ Thừa Lớn Nhất ( Bản Khó )

---

**Author :** **Not NTT_36**🐧🐧🐧
**Link  :** https://lqdoj.edu.vn/problem/maxpowerhard
Để làm bài này chúng ta cần biết về ***[Công thức Legendre](https://vi.wikipedia.org/wiki/C%C3%B4ng_th%E1%BB%A9c_Legendre#Ch%E1%BB%A9ng_minh)*** . 
> Công thức này được lụm từ một editorial nào đó của anh flo(orz)
- Gọi $v_p(n)$ là số mũ lớn nhất của $p$ , sao cho $n$ ⋮ $p$$^{số mũ đó}$ . Trong **công thức Legendre** ta biết : Nếu $p$ là một số nguyên tố , thì ta có thể áp dụng **công thức Legendre** (tức v$_p$($n!$) = int($n/p$)+int($n/p$²)+....+int($n/$$p^{int(log_p(n))}$))
- Nhưng nếu $p$ không phải là số nguyên tố , thì nếu tính như vậy sẽ sai . Nên ta có thể dùng **Phân tích thừa số nguyên tố** để tính:
    -  Ta sẽ phân tích các thừa số nguyên tố của $p$ ra , và với mỗi thừa số nguyên tố , ta áp dụng **công thức Legendre** để tính ( $v_{thừa số đó}(n!)$ ) , sau đó , ta sẽ chia lấy thương kết quả vừa tính ra được với số lượng thừa số đó (**Ví dụ** $24 = 2 * 2 * 2 * 3$ , có $3$ thừa số $2$ thì ta chia kết quả cho $3$ , $1$ thừa số $3$ thì ta chia kết quả cho $1$) 
    - Đáp án cuối cùng của chúng ta chính là là min của các kết quả đó. 
- Thêm một điều kiện nữa là nếu kết quả cuối cùng == $0$ thì ta sẽ xuất $-1$

**Code mẫu tham khảo( Không chắc AC ):**
https://ideone.com/nCDkJT

