#24 [C++]. Kiến Thức Toán Và Lý Thuyết Số Quan Trọng Trong Lập Trình Phần III

[@28tech_]

Thông tin các khóa học mình đang hướng dẫn : 28tech.com.vn/

[@28tech_]

59:00 : Mình quên mất chưa chia dư cho res vs (1e9+7). Mọi người chú ý thêm res %= MOD sau dòng 62. Một số bài toán áp dụng kiến thức ở trên Phép toán Modulo : cses.fi/problemset/task/1095 cses.fi/problemset/task/1712 Sol : ideone.com/UKqiWL Tổ hợp : cses.fi/problemset/task/1079 cses.fi/problemset/task/1715 Nghịch đảo modular : cses.fi/problemset/task/1716 Fibonacci number : cses.fi/problemset/task/1722

[@BDCAT_VuNgocPhuong]

em tưởng res+=a[i][k] *b[k][j] % mod là dc rồi vẫn phải chia dư tiếp ạ 59:45

[@HatGiongTamHon896]

​@@BDCAT_VuNgocPhuong phải lấy dư của res nữa vì toán tử cộng bằng lấy giá trị của cả cụm (a[i][k] *b[k][j] % mod) b ạ, nếu không lấy dư của res thì số to rất dễ bị tràn số

[@dovanchung9206]

Em thích nhất bài tổ hợp chập k của n :3

[@hoanginhnam6873]

cám ơn a be. bai hoc tuyet voi~!!!!!

[@28tech_]

Ok cái phần này thì hơi khoai vs em tú đấy :v

[@28tech_]

@Cong Lao ơi a ko đọc được bl của m. (x % m + m)%m để tránh nghịch đảo modul nó là số âm nhé.

[@quyenphamvan5321]

1:01:05 sao mảng res là ma trận đơn vị lại lấy giá trị là 1 0 0 1 vậy ạ

[@28tech_]

Ma trận đơn vị là ma trận có đường chéo chính là số 1

[@quyenphamvan5321]

@@28tech_ em cảm ơn ạ

[@nvnhuquynh4505]

a ơi, cho e hỏi là giải thích nhân ma trận a nói tới làm ở video nào v ạ

[@tienteocri3300]

cái ma trận trong bài tìm số fibonaci 1 1 1 0 đó có chứng minh được không anh ? ví dụ người ta cho chuỗi fibonaci dạng khác thì làm sao anh ?

[@codekhongngu]

a ơi cho em hỏi chỗ số fibonacii 59:04 sao lại tính ra res rồi phải đổ lại a[i][j] ạ

[@28tech_]

Không thì e phải return về 1 mảng 2 chiều, nó ko tiện lắm nên gán luôn kết quả cho ma trận a ý.

[@thaiphan1289]

thế ct (a*b) mod m có bằng ((a mod m) *b) mod m không ạ. Em thử thì nó vẫn đúng ạ

[@TrườngPhạm-t2k]

sao từ a*x%m=1 anh tim đc cái modular inversion theo: (x%m+m)%m vậy anh

[@haohoang8557]

dạ anh ơi sao em làm cái tổ hợp nghịch đảo modulo giống anh mà vẫn bị timelimit 2 case anh nhỉ, n,k cũng 1e6

[@28tech_]

Em làm trong contest của a ah?

[@haohoang8557]

@@28tech_ dạ bài của trường em ạ

[@28tech_]

@@haohoang8557 còn tuỳ cái chia dư cho số nào e. Nếu chia dư cho snt thì e dùng tính nghịch đảo modulo bằng fermat nhỏ

[@Jadenyuki676]

Bài tính số tổ hợp làm trên code ptit bị RTE(lỗi thực thi) anh ạ :((

[@SangNguyen-kr7qj]

anh có video nào hướng dẫn kĩ về powmod chưa ạ cho em xin với :

[@28tech_]

Hình như là chưa thì phải :v . Em xem trong danh sách phát lý thuyết số ý.

[@Sirfo4]

30:24 hơi khó hiểu cái đoạn lấy x ra như thế

[@Sirfo4]

ad giúp được không sao không đặt luôn là abs cho nhanh mà thêm mấy cái m hơi chóng mặt ạ :))

[@Sirfo4]

ad nếu mạnh về giải thuật toán thì nên giải thêm mấy bài ở trong leecode nữa

[@khavovan8201]

Thuật toán Euclid cơ bản ở đâu vậy a?

[@28tech_]

Nó là thuật toán tìm UCLN ấy. Ở phần 1 hay sao ấy

[@TaiTran-ib8wr]

Anh ơi cho em hỏi vì sao nếu (ax)%m=1 thì x luôn thuộc [1,m-1] vậy ạ?

[@TaiTran-ib8wr]

x là ngịch đảo modul của a theo m.

[@28tech_]

Nó quy định thế thôi em còn có nhiều giá trị thuộc ngoài khoảng kia vẫn thỏa mãn nhé.

[@HatGiongTamHon896]

bạn tưởng tượng nó như 1 chu kì ấy, trường hợp [1,m-1] có thể được hiểu là chu kì đầu tiên, các chu ki sau lần lượt là [m+1,2m-1]..[2m+1,3m-1] .... miễn là x không chia hết cho m là được b ạ

[@BDCAT_VuNgocPhuong]

Phần nghịc dao modul (x%M+M)%M là sao ạ,em ko hiểu lắm ạ

[@28tech_]

x tìm được từ thuật toán euclid mở rộng có thể âm nên xử lý như vậy để x thành dương.

[@PresidentQuyen]

Nhân ma trận tại sao lại gán lại vào mảng A vậy anh

[@Jadenyuki676]

vì ko return ma trận được :((

[@gianglo123]

ôi a vơi, cái tính fibo bằng nhân ma trận, dòng 68 a phải mod thêm lần nx, do học theo a mà e bị sai lỗi đó, làm mất 40đ lúc thi miền, tiếcccccc

[@28tech_]

😂😂😂😂 hahaa thiếu chút em a cũng ko để ý

[@gianglo123]

@@28tech_ trời ơi a ơi, e mất 40 đ nên bị trật luôn, tiếc thực sự mới thi tuần trước

[@haohoang8557]

dạ chia cho 1e9+7 nên em làm cái snt ạ, sao em phản hồi mà nó không hiện nên em cmt ở đây luôn ạ

[@28tech_]

Thế thì e áp dụng định lí nhỏ fermat ấy. Có thể do tài khoản của e

[@fruith_]

Cái chỗ anh viết extended xong không return để dừng đệ quy mà nó vẫn chạy được à =))

[@28tech_]

Hơi non đấy hoàng ạ, hehe. Return thì nó kết thúc luôn còn ko return thì hết câu lệnh nó cũng kết thúc hàm mà

[@fruith_]

@@28tech_ À dạ hehe hóa thân chú bé đần =)))

[@MinhLe-fw3kz]

anh cho em xin file tài liệu với ạ

[@lamduong6906]

anh ơi cho em hint về lũy thừa a^b^c % MOD với ạ ,em cảm ơn anh

[@28tech_]

Em áp dụng định lí nhỏ fermat để giảm số mũ b^c xuống nhé

[@NguyenNgocTuan-A-bv2ww]

có phần 4 ko bạn

[@28tech_]

Không có bạn ơi, mấy kiến thức còn lại thì m.n tự tìm hiểu thêm.

[@jeager6588]

int x , d , y ; void extended(int a , int b){ if(b==0){ x = 1 ; y = 0 ; d = a ; } else{ extended(b,a%b) ; int temp = x ; x = y ; y = temp - a/b * y ; } } cho em hỏi đoạn quay ngược từ câu lệnh else xog đệ quy thì mình quay lùi là sao ạ vì đệ quy xog x = 1 ; y = 0 ; mà x = y ; y = temp - a/b * y ; cho a =55 ; b= 80 thay vào là x= 0 ; y = 1 - 5/0 * 0 ( vì khi đệ quy thì (5,0) tức là a = 5 , b = 0 )

[@28tech_]

Em bị nhầm 1 chút về giá trị của a, b. Giá trị a, b của em khi b = 0 thì hàm đệ quy dừng, nhưng khi đó giá trị a % b mới là = 0, và tính toán x, y theo giá trị của a, b trước khi b = 0 chứ. Em xem lại xem có đúng ko. Extended(b, a % b) dừng khi a % b == 0 và mình tính toán với a, b mà chứ có tính toán với b, a % b đâu.

[@jeager6588]

em cảm ơn em làm đc r anh ! nó đệ quy ngược lại không biết cách làm như này có đúng k vd 15 20 thì đệ quy temp =1 15 20 x = -1 ; y = 1 - 0* -1 temp =0 20 15 x = 1 , y = 0 - 1 * 1 ; temp =1 15 5 x = 0 ; y = 1 - 15/5 * 0 5 0 x = 1 ; y =0 => x = -1 ; y =1 ; 15 * -1 + 20 *1 = 5 55 với 80 cũng đúng vs cách trên :V

[@Mot-cong-mot-la-hai]

@@28tech_ em cũng thắc mắc phần này ạ, tại sao trong hàm này không có lệnh return, vì có lệnh return hàm mới lưu giá trị được.

[@TrungTran-cs1wt]

const int MOD = (int)1e9 + 7; using ll = long long; ll pwr(ll a, ll b) { a %= MOD; ll tich = 1; for (int i = 0; i < b; i++) { tich *= a; tich %= MOD; } return tich % MOD; } int main() { int n; cin >> n; for (int i = 0; i < n; i++) { ll a, b, c; cin >> a >> b >> c; ll result = pwr(pwr(a, b), c); cout

[@28tech_]

Này e phải dùng định lí nhỏ fermat để giảm mũ xuống e ạ. Vs tính pwr phải dùng luỹ thừa nhị phân