Tính Toán Số Học

[bills_khoa]

Giả sử x,y,z là các số nguyên dương 4byte

A. viết hàm tính X mũ m MOD y // ( X^m mod y)
b. viết hàm tính USCLN của Xmũ m và y //( USCLN của X^m và y)
chú y rằng giá trị cùa X mũ m có thể rất lớn.

[huynguyen]

Ko đem bài tập cá nhân lên đây đánh đố người khác như thế, vi phạm quy định forum rồi nhé.

[rox_rook]

Giả sử x,y,z là các số nguyên dương 4byte

A. viết hàm tính X mũ m MOD y // ( X^m mod y)
b. viết hàm tính USCLN của Xmũ m và y //( USCLN của X^m và y)
chú y rằng giá trị cùa X mũ m có thể rất lớn.

Học danh sách liên kết chưa ?

[bills_khoa]

Hi các tiền bối. Sao a Huynguyen lại nói vậy khi tôi đang cần sự giúp đỡ. Đây là những bài tập khó trong lớp tôi học và chưa giải ra được nên đưa lên nhờ anh em giải giúp. Sao lại gọi là bài tập cá nhân hay bài tập của tập thể cộng đồng? Khái niệm này thật mới.
Thưa bác Rox_rook là em đã học rồi. gờ chỉ cần bác viết ra hoặc đưa ra thuật toán giúp em thôi.
Thanks

[rox_rook]

Bài này nếu bạn đã nói khó thì bạn phải đưa idea lên thì người khác mới giúp được. Mod cũng là sinh viên thôi bạn ạ, chẳng qua học trước 1 tí chứ không có nghĩa là biết tất cả hay thuộc loại siêu hạng mới được làm mod.

Thưa bác Rox_rook là em đã học rồi. gờ chỉ cần bác viết ra hoặc đưa ra thuật toán giúp em thôi.

Và điều này chắc chắn là làm sao tui giải liền cho bạn được, tui cũng phải suy nghĩ và làm như bạn thôi, nếu bạn thực sự muốn học thì ok tui sẽ giúp trên phương diện cả 2 cùng làm. Hiện tại đang đầu tuần nên tui rất bận, nếu được thì cuối tuần tui sẽ tranh thủ suy nghĩ thử ( và nhớ là không chỉ có mình tui suy nghĩ ). Cái tui muốn thấy đầu tiên là suy nghĩ của bạn tới đâu rồi, vì bạn đã hỏi tức là bạn đã suy nghĩ rất sâu mà không có cách giải quyết. Còn nếu bạn nói bạn chưa suy nghĩ gì thì tui cũng chẳng rảnh để giúp bạn đâu nhé.
Cả 2 bài đọc sơ qua thì tui thấy cái x mũ m thì dùng danh sách liên kết cho số lớn là hoàn toàn có thể giải quyết được, chỉ còn là vấn đề xử lý cái modulo và UCLN của số lớn này với y mà thôi.
Một vấn đề nữa là cái đề của bạn không rõ ràng cho y, y range của nó là bao nhiêu, số thật lớn cũng được ?

[bills_khoa]

Ai Za!!! Bác Rox_rook ah! Em đọc nhiều và làm nhiều bài này rồi nhưng nó vẫn chưa ra. Em suy nghĩ cách để làm tối ưu nó. Chẳng hạn em đùng Đệ quy để viết hàm X mũ m rồi. chứ nếu dùng các hàm for để tính X mũ m thì wá đơn giản. Sau đó em phải viết tiếp một hàm có tên là MOD để tính tiếp phần chia cho y. Còn y là bao nhiêu thì bác phải xem cái đề bài vì nó là số nguyên dương 4 byte.

[bills_khoa]

Ở câu b: Hàm tìm USCLN của 2 số nguyên thì wá đơn giản rồi. Em muốn các bác chú ý cái đề bài vì người ta nói có thể X mũ m nào đó là rất lới nên nếu dùng cách thông thường thì sẽ lâu. Hãy tìm cách nào đó cho nó thuận tiện và nhanh nhất.

[rox_rook]

Tui không có ý gây sự với cậu, chẳng có lợi ích gì vả lại là mod tui cãi với bạn thì chắc ở đây ai cũng bênh tui . ( chắc trừ tên nhc ) T_T. Nhưng tui ghét nhất là những câu như thế này:
-Giải dùm gửi mail.
-Giải nhanh dùm mình nhé.
-Mai phải nộp bài rùi.
Tui ghét lười và ghi kiểu ra lệnh người khác + chờ nước tới chân mới nhảy. Nếu tui đọc những câu đại loại như vậy tui sẽ không bao h giúp, vì đối với tui những người có tư tưởng thế này thì có giúp cũng chỉ phí công.
Còn về bài đó :

Ai Za!!! Bác Rox_rook ah! Em đọc nhiều và làm nhiều bài này rồi nhưng nó vẫn chưa ra. Em suy nghĩ cách để làm tối ưu nó. Chẳng hạn em đùng Đệ quy để viết hàm X mũ m rồi.

Tại sao đệ qui tối ưu hơn 1 vòng lặp cậu nói tui nghe xem ? Một vòng lặp không rõ ràng hơn à. Độ phức tạp của lời gọi đệ qui và vòng for là bao nhiêu, bigO(n) ? Có gì khác biệt giữa vòng lặp và đệ qui chỗ đó.
Còn cái số lớn thì làm sao mà làm cái đùng thế được, cậu nói với tui cậu học DSLK rùi mà cậu nói thế đó hả. Vượt qua 4 triệu thì sao ? Danh sách liên kết thì phải cài đặt rắc rối hơn nhiều. Nếu cậu thực sự chưa học qua thì tui khuyên tạm hoãn bài này lại. Còn nếu học qua rùi thì dùng list của STL mà làm. Tính cho ra cái X mũ M số lớn rùi hãy suy nghĩ đến giải thuật tính mod và UCLN.

[AlexF]

bill khoa à,tớ chưa học tới phần danh sách liên kết,nếu pác nào hảo tâm có thể cho mình biết mod là cái gì không nhỉ,,kái định nghĩa lạ quá x mũ m mod y(đó là kái gì)tớ đang suy nghĩ bài này nhưng mà gặp mấy kái này không hiểu lắm