VM 10 Bài 08 - Tích
Xem dạng PDF
Gửi bài giải
Điểm:
0,78 (OI)
Giới hạn thời gian:
0.6s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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
Bình luận
nếu code vét big num bài này thì đc bao nhiêu test ạ
import sys import math def inputk(): return sys.stdin.readline() def printk(s): sys.stdout.write(s) n=int(inputk()) i=1 j=1 while not i==7: if int(math.factorial(i)/math.factorial(j-1))==n: printk(str(j)+" "+str(i)) break if int(math.factorial(i)/math.factorial(j-1))<n: i+=1 if int(math.factorial(i)/math.factorial(j-1))>n: j+=1
code em nhu nay co dung ko moi nguoi
ban can hoc cach hoi bai truoc khi hoc code
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ỉ?
Ý 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.
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 :)).
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bạn để P kiểu int thì code này sao chạy đc :v