Số chính phương (HSG12'18-19)

View as PDF

Points: 300 (p) Time limit: 1.0s Memory limit: 256M Input: stdin Output: stdout

Số chính phương là số tự nhiên có căn bậc 2 là một số tự nhiên, hay nói cách khác, số chính phương có thể biểu diễn dưới dạng bình phương (lũy thừa bậc 2) của một số tự nhiên. Ví dụ: 4 là số chính phương, vì \(4=2^2\) ; 9 là số chính phương, vì \(9=3^2\).

Bờm rất thích các số chính phương, muốn tìm hiểu về nó, và biết rằng số chính phương cũng được biểu diễn bằng tích của một tập các số tự nhiên phân biệt. Chẳng hạn: \(9=1 \times 9\); \(144=2 \times 3 \times 4 \times 6\). Bờm hay ngẫm nghĩ về nó mọi lúc khi có thời gian rảnh. Hôm nay, giờ giải lao trên lớp, Bờm quay sang đố Tuấn: “Với số tự nhiên \(N\) cho trước, tìm số chính phương lớn nhất bằng tích của một tập các số tự nhiên phân biệt được lấy từ tập các số từ 1 đến \(N\)”. Tuấn suy nghĩ mãi mà chưa trả lời được câu đố mà thời gian thì ít quá.

Yêu cầu: Cho một số nguyên \(N\), hãy giúp Tuấn đưa ra số chính phương lớn nhất bằng tích của một tập các số tự nhiên phân biệt được lấy từ tập các số từ 1 đến \(N\). Số đó có thể rất lớn nên chỉ cần xuất ra phần dư khi chia số đó cho 1000000007 \((10^9 + 7)\).

Input

  • Một dòng duy nhất chứa số nguyên dương \(N\) \((N \leq 4 \times 10^4­)\).

Output

  • Ghi ra một dòng duy nhất là kết quả bài toán sau khi đã \(mod\) \(1000000007\).

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(N \leq 10^2\).
  • Subtask \(2\) (\(30\%\) số điểm): \(N \leq 10^3\).
  • Subtask \(3\) (\(40\%\) số điểm): \(N \leq 4 \times 10^4\).

Example

Test 1

Input
5 
Output
4

Comments


  • 119
    HDfake1    7:27 p.m. 16 apr, 2021 edited

    Spoiler Alert

    Approach

    • Dựng mảng \(factor[i]\) = số lượng thừa số \(i\) trong \(n!\) khi phân tích \(n!\) thành thừa số nguyên tố

    Duyệt \(j\) từ \(2\) đến \(n\), phân tích \(j\) thành thừa số nguyên tố trong \(sqrt(n)\) hoặc \(log(n)\) bằng sàng

    • Để đảm bảo kết quả nhận được là số chính phương, ta sẽ trừ các \(factor[i]\) đi \(1\) nếu \(factor[i] >= 1\)\(factor[i]\) lẻ
    • Kết quả = tích các \(i^{factor[i]}\) với \(i = 2 ... n\)

    Prove

    • Vì mỗi thừa số nguyên tố ta lấy số mũ chẵn lớn nhất của nó nên kết quả thu được sẽ lớn nhất

    Reference AC code | \(O(nlogn)\) time

    https://pastebin.com/RPziufrG


    Do đây là lần đầu em viết editorial nên còn sơ sài, mong mọi người góp ý và đừng downvote em, em cảm ơn 🙁