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 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ố
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
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 ạ
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 )
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.
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
![#25 [C++]. Giải Thích Cách Hàm Đệ Quy Hoạt Động | Kỹ Thuật Đệ Quy Trong C++](http://i.ytimg.com/vi/eQ3VpTtc9lE/mqdefault.jpg)
![#25 [C++]. Giải Thích Cách Hàm Đệ Quy Hoạt Động | Kỹ Thuật Đệ Quy Trong C++](/img/tr.png)
![#19.5 [C++]. Các Hàm Thuật Toán Thông Dụng Trong Thư Viện Algorithm C++](http://i.ytimg.com/vi/v7KL3b2-Zlo/mqdefault.jpg)
![#19.1. [C++]. Thuật Toán Sắp Xếp Chèn | Sắp Xếp Nổi Bọt | Sắp Xếp Chọn | Sắp Xếp Đếm Phân Phối](/img/n.gif)
Thông tin các khóa học mình đang hướng dẫn : 28tech.com.vn/
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
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
@@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ố
Em thích nhất bài tổ hợp chập k của n :3
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 ?
cám ơn a be. bai hoc tuyet voi~!!!!!
Ok cái phần này thì hơi khoai vs em tú đấy :v
@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é.
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 ạ
sao từ a*x%m=1 anh tim đc cái modular inversion theo: (x%m+m)%m vậy anh
thế ct (a*b) mod m có bằng ((a mod m) *b) mod m không ạ. Em thử thì nó vẫn đúng ạ
Bài tính số tổ hợp làm trên code ptit bị RTE(lỗi thực thi) anh ạ :((
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 ạ
Ma trận đơn vị là ma trận có đường chéo chính là số 1
@@28tech_ em cảm ơn ạ
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 ạ
Thế thì e áp dụng định lí nhỏ fermat ấy. Có thể do tài khoản của e
anh có video nào hướng dẫn kĩ về powmod chưa ạ cho em xin với :
Hình như là chưa thì phải :v . Em xem trong danh sách phát lý thuyết số ý.
ô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
😂😂😂😂 hahaa thiếu chút em a cũng ko để ý
@@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
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
Em làm trong contest của a ah?
@@28tech_ dạ bài của trường em ạ
@@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ỏ
Thuật toán Euclid cơ bản ở đâu vậy a?
Nó là thuật toán tìm UCLN ấy. Ở phần 1 hay sao ấy
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] ạ
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 ý.
Cái chỗ anh viết extended xong không return để dừng đệ quy mà nó vẫn chạy được à =))
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à
@@28tech_ À dạ hehe hóa thân chú bé đần =)))
có phần 4 ko bạn
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.
Phần nghịc dao modul (x%M+M)%M là sao ạ,em ko hiểu lắm ạ
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.
anh ơi cho em hint về lũy thừa a^b^c % MOD với ạ ,em cảm ơn anh
Em áp dụng định lí nhỏ fermat để giảm số mũ b^c xuống nhé
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
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
anh cho em xin file tài liệu với ạ
Anh ơi cho em hỏi vì sao nếu (ax)%m=1 thì x luôn thuộc [1,m-1] vậy ạ?
x là ngịch đảo modul của a theo m.
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é.
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 ạ
Nhân ma trận tại sao lại gán lại vào mảng A vậy anh
vì ko return ma trận được :((
30:24 hơi khó hiểu cái đoạn lấy x ra như thế
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 ạ :))
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
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 )
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.
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
@@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.