VM 10 Bài 08 - Tích

View as PDF

Submit solution

Points: 0.78 (partial)
Time limit: 0.6s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VM10Tác giả: Cosmin Gheorghe
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho một số ~P~ (~1 \le~ ~P~ ~\le 10^{20000}~). Tìm hai số tự nhiên ~X~ và ~Y~ sao cho ~X \times~ ~(X+1)~ ~\times \dots \times Y = P~.

Input

Một số ~P~ duy nhất. Dữ liệu vào đảm bảo luôn tìm được kết quả ~X~, ~Y~ thỏa mãn sao cho ~1 \le X \le Y \le 10^{5}~.

Nếu có nhiều đáp án thỏa mãn với ~1 \le X \le Y \le 10^{5}~, chọn đáp án có ~X~ nhỏ nhất.

Output

In ra hai số ~X~, ~Y~.

Sample Input

60

Sample Output

3 5

Comments

Please read the guidelines before commenting.



  • 7
    koffte   commented on Sept. 7, 2021, 7:15 p.m.

    Chào các bạn.

    Ban đầu mình tự cài bignum trên C++ nhưng bị chạy quá thời gian, nên chuyển sang Python 3 cũng vẫn không được. Các bạn có gợi ý cải tiến gì không nhỉ?

    Code C++ của mình ở đây

    Code Python của mình ở đây.

    Ý tưởng thuật toán mình lấy ở đây nhé.

    Cảm ơn các bạn đã dành thời gian giúp mình.


    • 8
      darkkcyan   commented on Sept. 7, 2021, 10:48 p.m.

      Việc sử dụng số lớn, 1 là không ổn trong bài này, chi phí cho làm việc với số lớn là quá lớn. Tỉ dụ 1 phép nhân/chia làm trong ~O(len)~ với ~len~ là số chữ số, vậy độ phức tạp ít nhất phải là ~O(n\times len)~, mà ~len~ còn có thể lớn hơn cả ~n~, do đó chương trình sẽ chạy rất chậm. Nhưng thứ 2 là bài này có thể giải không sử dụng số lớn, và cái đó là cái key idea của bài, nên bạn chịu khó suy nghĩ thêm, hoặc tham gia VNOI discord để thảo luận :)).


  • -28
    khanhuit   commented on July 22, 2021, 4:51 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 3
      NoobCpp   commented on Aug. 17, 2021, 7:30 p.m.

      Bạn để P kiểu int thì code này sao chạy đc :v