Tìm Số Nguyên Nhỏ Nhất Chia Hết Cho Các Số Từ 1 đến N

Có thể bạn quan tâm

programmingc++ Tu_Tran (Tú Trần) August 30, 2020, 9:43am #1 Lại là mình đây ạ, mình có đề bài đơn giản như này ạ:Cho số tự nhiên n. Nhiệm vụ của bạn là tìm số nguyên nhỏ nhất chia hết cho 1, 2, …, n. Input:

Dòng đầu tiên đưa vào T là số lượng bộ test.

T dòng tiếp theo mỗi dòng đưa vào một bộ test. Mỗi bộ test là một số tự nhiên n.

T thỏa mãn ràng buộc: 1≤T≤10^4;

Output: Đưa ra kết quả mỗi test theo từng dòng.

image843×243 3.78 KB Lỗi Time Limited Exceed trong bài code này là sao ạ? Mọi người check code giúp mình với ạ. Mình không giỏi code lắm, mong mn chỉ giáoUpdate chút là code mình đã fix lại tí nhưng giờ lại bị Wrong Answer :((2 Likes nguyen2812 (Bùi Đình Nguyên) August 30, 2020, 9:37am #2 Nếu là nộp bài trên máy của trường thì đây không phải lỗi gì cả. Chương trình vẫn bình thường. Vượt quá thời gian 1 tẹo thôi. Có lẽ là cần tìm 1 hướng làm khác tốt hơn, tốn ít thời gian hơn. Có vài cách giảm thời gian đây. Không khuyến khích sử dụng printf() hoặc scanf() thay cin, cout nhé.

How to overcome Time Limit Exceed(TLE)? - GeeksforGeeksA Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.5 Likes Tu_Tran (Tú Trần) August 30, 2020, 9:39am #3 okay, tks bạn. mình có update lại rồi đó, bạn xem giúp mình đc không ah

noname00 (HK boy) August 30, 2020, 9:50am #5

return (a*b)/GCD(a,b);

Ở đây có vẻ có tràn số

4 Likes Tu_Tran (Tú Trần) August 30, 2020, 9:51am #6 thế nên mình để unsigned long int rồi đó ạ nguyen2812 (Bùi Đình Nguyên) August 30, 2020, 9:54am #7 Đến 8 bytes rồi vẫn tràn. Có lẽ phải chia trước rồi nhân thôi. @Tu_Tran đổi như anh nào đấy gợi ý ở topic cũ xem sao.thành :6 Likes Tu_Tran (Tú Trần) August 30, 2020, 9:51am #8 Thực ra n chỉ là số tự nhiên thôi ạ, mình làm bộ đệm hơi thừa Tu_Tran (Tú Trần) August 30, 2020, 9:55am #9

return ( a / GCD(a,b) ) * b;

không được bạn ạ :(( . Bạn check xem hàm main có sai về mặt thuật toán không với ah kisuluoibieng (Tên Gì Cũng Được) August 30, 2020, 10:00am #10 Bội chung nhỏ nhất của a, b, c Bằng Bội chung nhỏ nhất của (bội chung nhỏ nhất của a, b) và c4 Likes Tu_Tran (Tú Trần) August 30, 2020, 10:00am #11 yep, tư tưởng của mình là thế đấy ạ. B xem hàm main của mình có ổn không kisuluoibieng (Tên Gì Cũng Được) August 30, 2020, 10:06am #12 10k bộ test, tất nhiên không thể chạy 10k lần Những gì đã tính rồi thì không tính lại Lưu lại các giá trị đã tính bằng mảng thôi6 Likes noname00 (HK boy) August 30, 2020, 10:11am #13

n chỉ là số tự nhiên

Không rõ miền giá trị của n là bao nhiêu, mình thử tính chay với 1 số giá trị:

n = 50: 3099044504245996706400 (vượt max unsigned long long int)

n = 100: 69720375229712477164533808935312303556800

n = 3000:

22847894461813938324787222822295155626520232915824216105237897774727805140633168105820168598673665297737394363821893982077026488296602937720046364807587773796489783025226944516941046518450937017171785429431141987073696631513313312061633862695434988202568124031286571062333808079173774207670322971595068770115533134590866132761918466460637548134776251481209468487526830582994356063094582472919447686130281485594115245104783149522711182729241824706344381821536894504587283040900827475286886950352821165085243564154061343889964037553703329221474171037012337811072503963971246910441908932129168594480355234289302387626156176473792348927061794209178056169089968011349097613966353675079396003768506338930453318707549810703556166830751828090694300019026057410096573042343781107668206481428946487524489812637018569741858703026588634965923079160607677473435779415792703366320947220764530760950817851731487336611087118693032362060404630553487423847190874070444264355809840084886190614554426444914865140243591092320319334091591102170975335724328691661681664220767422457749579893554961073088330544578434610715585367551345174895209070231775187043423074291450445741940455756523233475867249562806024826006078088655728105057622080277344458682271292589931416026728802463640459349760312887533423223581399704459945857280000

n = 30000: hiển thị mất tầm 163 dòng, mỗi dòng là 81 ký tự.

Vấn đề của bạn không phải là bạn muốn tính trong khoảng unsigned long long là được.4 Likes nguyen2812 (Bùi Đình Nguyên) August 30, 2020, 10:44am #15 Muốn tính với n bất kì có lẽ phải dùng string mất

. Chắc phải có giới hạn n thôi.

không được bạn ạ

Có câu này nữa thì 99.99% là cộng trừ nhân chia với string cho vui nha. rogp10 (rogp10) August 30, 2020, 10:57am #16 Bài này ko cần phép chia

mà nhân bắt cặp đầu cuối là nhanh nhất.Ngoài cách tính UCLN bằng Euclid thì còn cách dùng phân tích thừa số

giờ chỉ còn tìm số mũ đúng nữa thôi.6 Likes tntxtnt (‏) August 30, 2020, 11:45am #17 unsigned long int != unsigned long long int nha6 Likes Tu_Tran (Tú Trần) August 30, 2020, 1:30pm #18 mình để là unsigned long long int luôn, mà vẫn bị Wrong tntxtnt (‏) August 30, 2020, 1:57pm #19 sao trong main() lại đi xài int cho bcnn của n số :V :V Sao lại đặt tên là temp mà ko đặt tên khác cho dễ hiểu :V8 Likes Tu_Tran (Tú Trần) August 30, 2020, 1:57pm #20 oh shitt, tks bác Giờ mới để ý, chỉnh sang unsigned long long int dc rồi bác ^^ , cảm ơn bác ở bài này nữa ạ