7 Chương trình. 10 Chương trình. 14 Tìm ước số chung lớn nhất. 14 Tìm bội số chung nhỏ nhất.
15 Phương pháp lọc theo khối. 17 Tìm nghịch đảo theo giải thuật Euclid mở rộng. 21 ATHENA IX Page 1 of 206 Kỹ thuật lập trình Giải thuật. 21 Chương trình.
25 Công thức tính tất cả các nghiệm. 25 Xác định số lượng nghiệm và dẫn xuất tất cả nghiệm thuộc đoạn cho trước. 26 Tìm nghiệm có tổng nhỏ nhất trên đoạn cho trước. 30 Giải thuật dựa trên cơ sở tìm phần tử nghịch đảo.
31 Dẫn xuất về phương trình Diophantine. 32 Trường hợp k – nguyên tố. 35 Hàm tính giai thừa rút gọn theo mô đun p. 37 Mối quan hệ với hàm Euler.
37 Giải thuật tìm căn gốc. 37 ATHENA IX Page 2 of 206 Kỹ thuật lập trình Đánh giá độ phức tạp. 38 Chương trình:. 40 Giải thuật tìm một nghiệm.
40 Tìm tất cả các nghiệm khi biết một nghiệm. 40 Chương trình. 43 Biểu diễn số. 44 Tổng hai số.
45 Chương trình minh họa. 50 Phân số liên tục (Continued fractions). 50 Giải thuật Leman phân tích số nguyên ra thừa số. 59 Chương trình.
61 Chương trình. 63 ATHENA IX Page 3 of 206 Kỹ thuật lập trình. 65 Chương trình. 67 Chương trình.
75 Giải thuật Graham. 75 Chương trình. 78 Chương trình. 82 Chương trình.
86 Chương trình:. 108 ATHENA IX Page 4 of 206 Kỹ thuật lập trình. 155 Ví dụ về ô tô mát hậu tố. 156 Giải thuật xây dựng ô tô mát hậu tố với chi phí thời gian tuyến tính.
156 Một số tính chất của ô tô mát hậu tố. 164 Ứng dụng ô tô mát hậu tố. 177 ATHENA IX Page 5 of 206 Kỹ thuật lập trình. 191 Quy hoạch động đơn giản.
204 ATHENA IX Page 6 of 206 Kỹ thuật lập trình Bài toán Cho 3 số nguyên dương a, n và p. Hãy tính an mod p. Dữ liệu: Vào từ file văn bản FASTPOWER.INP gồm một dòng chứa 3 số nguyên dương a, n và p (1 ≤ a ≤ 109, 1 ≤ n ≤ 1018, 1 ≤ p ≤109). Kết quả: Đưa ra file văn bản FASTPOWER.OUT một số nguyên – kết quả tìm được.OUT 2 9 10 2 Giải thuật Việc yêu cầu đưa ra theo mô đun p là để đảm bảo các kết quả trung gian và cuối cùng là đủ nhỏ, không cần xử lý số lớn, Bản chất của vấn đề là phải tính nhanh xy, trong đó x, y là các số nguyên dương.
Giả thiết y có dạng biểu diễn nhị phân là y = (bm, bm-1,., b1, b0), trong đó bi là 0 hoặc 1, i = 0 ÷ m-1, bm = 1. Ví dụ: y = 910 = 10012 = 𝟐𝟑 + 𝟐𝟎 b3 b2 b1 b0 Ta có 𝒊 𝒊 xy = ∏𝒎 𝒊=𝟎 𝒙 𝒃𝒊 𝟐 = ∏𝒎 𝒊=𝟎,𝒃𝒊 =𝟏 𝒙 𝟐 (*) 𝒊 Như vậy ta phải tính x1, x2, x4, x8,. , 𝒙𝟐 𝒊 Để tính 𝒙𝟐 ta chỉ cần thực hiện i phép nhân: x → x×x = x2 → x2×x2 = x4 → x4×x4 = x8 →. ATHENA IX Page 7 of 206 Kỹ thuật lập trình Như vậy để tích lũy tích (*) ta cần thực hiện không quá 2×m phép nhân, tức là với chi phí thời gian O(log2y).
Chương trình #include <bits/stdc++.h> #define NAME "fastpower." using namespace std; ifstream fi (NAME"inp"); ofstream fo (NAME"out"); int64_t a,n,p,ans=1; int main() { fi>>a>>n>>p; a%=p; while(n) { if(n&1)ans=(ans*a)%p; a=(a*a)%p; n>>=1; } fo<<ans; } Nhận xét Có thể lập luận theo sơ đồ xử lý đệ quy, chặt chẽ hơn về mặt lý thuyết nhưng chỉ phù hợp với kỹ thuật lập trình đệ quy, chương trình chẳng những không ngắn gọn mà còn tốn bộ nhớ và thời gian thực hiện hơn sơ đồ lặp đã nêu ở trên: xét việc tính r = xy, (x, y – nguyên dương), nếu y chẵn ta có r = xy/2×xy/2, còn với y lẻ ta có: r = x(y-1)/2×x(y-1)/2×x, tức là với một hoặc 2 phép nhân ta đã giảm độ lớn của số mũ xuống một nửa. Như vậy với không quá 2×log2y ta có số mũ của lũy thừa là 0. ATHENA IX Page 8 of 206 Kỹ thuật lập trình Trong các tài liệu, sơ đồ nhân Ai Cập còn được gọi với nhiều tên khác. Việc chứng minh tính đúng đắn và hiệu quả của Sơ đồ nhân Ai Cập cũng tương tự như đối với việc tính nhanh lũy thừa.
Nói chung trong phần lớn các trường hợp sơ đồ đệ quy sẽ cho chương trình ngắn gọn hơn sơ đồ lặp, nhưng trong thực hiện – tốn bộ nhớ hơn và thời gian tính cũng lớn hơn, Chương trình Nhân Ai Cập: #include <bits/stdc++.h> #define NAME "egypmul." using namespace std; ifstream fi (NAME"inp"); ofstream fo (NAME"out"); int64_t a,b,p,ans=0; int main() { fi>>a>>b>>p; a%=p; while(b) { if(b&1)ans=(ans+a)%p; a=(a<<1)%p; b>>=1; } fo<<ans; } ATHENA IX Page 9 of 206 Kỹ thuật lập trình Bài toán Dãy số F0 = F1 = 1, Fi = Fi-1 + Fi-2 với i > 1 được gọi là dãy số Fibonacci.Cho 2 số nguyên dương n và p. Hãy tính và đưa ra Fn theo mô đun p. Dữ liệu: Vào từ file văn bản FIB.INP gồm một dòng chứa 2 số nguyên n và p (1 ≤ n ≤ 1018, 0 < p ≤ 109). Kết quả: Đưa ra file văn bản FIB.OUT một số nguyên số Fn theo mô đun p.OUT 11 100 44 Giải thuật Dãy số Fibonacci là dãy số tăng rất nhanh.
Do dãy số này có rất nhiều ứng dụng cả trong lý thuyết lẫn thực tế nên nó đã được khảo sát rất kỹ. Có nhiều công thức tính số Fibonacci đã được xác định. Với tin học công thức tính phù hợp nhất là công thức ma trận, đảm bảo độ phức tạp O(logn) và không phải giải quyết vấn đề tích lũy sai số làm tròn. Xét 2 ma trận vuông kích thước 2×2: 𝑎00 𝑎01 𝑏00 𝑏01 A = (𝑎 𝑎11 ), B = ( ), ta có A×B = C, trong đó 10 𝑏10 𝑏11 𝑐00 𝑐01 𝑎 × 𝑏00 + 𝑎01 × 𝑏10 𝑎00 × 𝑏01 + 𝑎01 × 𝑏11 C = (𝑐 𝑐 ) = ( 00 ) 10 11 𝑎10 × 𝑏00 + 𝑎11 × 𝑏10 𝑎10 × 𝑏01 + 𝑎11 × 𝑏11 Để thuận tiện tính toán ta tuyến tính hóa ma trận 2 chiều thành một chiều: 𝑎00 𝑎01 𝑥0 𝑥1 A = (𝑎 𝑎11 ) = ( 𝑥2 𝑥3 ), 10 𝑏 𝑏01 𝑦0 𝑦1 B = ( 00 ) = (𝑦 𝑦 ), 𝑏10 𝑏11 2 3 𝑐00 𝑐01 𝑧0 𝑧1 C = (𝑐 10 𝑐11 ) = ( 𝑧2 𝑧3 ), trong đó z0 = x0×y0+x1×y2, z1 = x0×y1+x1×y3, z2 = x2×y0+x3×y2, z3 = x2×y1+x3×y3.
Công thức ma trận tính số Fibonacci: ATHENA IX Page 10 of 206 Kỹ thuật lập trình (𝐹𝑛−2 𝐹𝑛−1 ) × (0 1 ) = (𝐹𝑛 𝐹𝑛+1 ) 1 1 Từ đây ta có (𝐹0 𝐹1 ) × 𝑃𝑛 = (𝐹𝑛 𝐹𝑛+1 ), 0 1 Trong đó P ≡ ( ). 1 1 Bằng kỹ thuật tính nhanh lũy thừa có thể nhận được Pn với độ phức tạp O(logn). Chương trình #include <bits/stdc++.h> #define NAME "fib." using namespace std; ifstream fi (NAME"inp"); ofstream fo (NAME"out"); uint64_t n,a,ans,fib,t[4]={0,1,1,1},r[4]={0,1,1,1},tg[4],p; void mp2(uint64_t x[],uint64_t y[],uint64_t z[]) {tg[0]=(x[0]*y[0]+x[1]*y[2])%p; tg[1]=(x[0]*y[1]+x[1]*y[3])%p; tg[2]=(x[2]*y[0]+x[3]*y[2])%p; tg[3]=(x[2]*y[1]+x[3]*y[3])%p; z[0]=tg[0];z[1]=tg[1];z[2]=tg[2];z[3]=tg[3]; } int main() { fi>>n>>p; while(n) {if(n&1) mp2(r,t,r); mp2(t,t,t); n>>=1; } ans=r[2]%p; fo<<ans; fo<<"\nTime: "<<clock()/(double)1000<<" sec"; } ATHENA IX Page 11 of 206 Kỹ thuật lập trình Định nghĩa Hàm Euler Φ(n) (hay còn ký hiệu là φ(n)) là số lượng các số trong phạm vi từ 1 đến n nguyên tố cùng nhau với n. Nói một cách khác, đó là số lượng các số trong đoạn [1, n] có ước số chung lớn nhất với n là 1.
Các giá trị đầu tiên của hàm này: Φ(1) = 1, Φ(2) = 1, Φ(3) = 2, Φ(4) = 2, Φ(5) = 4. Tính chất Ba tính chất đơn giản sau đây cho phép tính hàm với n bất kỳ: Nếu p là số nguyên tố thì Φ(p) = p-1 Đó là điều hiển nhiên vì mọi số nguyên tố đều là nguyên tố cùng nhau với các số nhỏ hơn nó. Nếu p là số nguyên tố và a là số tự nhiên thì Φ(pa) = pa – pa-1 Thật vậy, pa chỉ không nguyên tố cùng nhau với các số dạng p×k, trong đó k là số nguyên và trong đoạn đang xét có tất cả pa/p = pa-1 số có thể đóng vai trò của k. Nếu a và b là nguyên tố cùng nhau thì Φ(a×b) = Φ(a) ×Φ(b) Xét z – số nguyên bất kỳ thỏa mãn điều kiện z ≤ a×b.
Gọi x và y là số dư của phép chia z tương ứng cho a và cho b. z nguyên tố cùng nhau với a×b khi và chỉ khi z nguyên tố cùng nhau với a và nguyên tố cùng nhau với b, điều này dẫn đến việc x nguyên tố cùng nhau với a và y nguyên tố cùng nhau với b. Theo định lý Số dư Trung Hoa, cặp số (x, y) như vậy (x ≤ a, y ≤ b) sẽ đơn trị xác định z ≤ a×b. Đó là điều phải chứng minh.
Giải thuật Hàm Euler được tính dựa trên việc phân tích số n ra thừa số nguyên tố. Nếu có ATHENA IX Page 12 of 206 Kỹ thuật lập trình trong đó pi là các số nguyên tố, i = 1 ÷ k, thì Hiệu quả của giải thuật phụ thuộc vào phương pháp phân tích n ra thừa số nguyên tố. Các phương pháp phân tích n ra thừa số nguyên tố với độ phức tạp thấp sẽ được xét sau. Dưới đây là phương pháp tính Φ(n) đơn giản nhất với độ phức tạp O(√𝑛).
Ứng dụng Tính chất quan trọng và thường được sử dụng là Định lý Euler: Trong đó a và m – nguyên tố cùng nhau. Trong trường hợp riêng, khi m là số nguyên tố, ta có Định lý nhỏ Ferma: Hàm Euler được ứng dụng trong việc giải nhiều bài toán thực tế cũng như các bài toán Olympic. ATHENA IX Page 13 of 206 Kỹ thuật lập trình Tìm ước số chung lớn nhất Ước số chung lớn nhất (Greatest Common Divisor – GCD) của 2 số nguyên không âm a và b là số nguyên lớn nhất mà a và b cùng chia hết cho số đó. Giải thuật Euclid cho phép tìm GCD với số lượng phép chia phải thực hiện là O(log(min{a, b})).
Giải thuật theo sơ đồ lặp: Giải thuật cũng có thể triển khai theo sơ đồ đệ quy: Do tính phổ biến của nhu cầu tìm GCD trong hệ thống lập trình C++ cung cấp hàm _ _gcd(a,b)trong thư viện của hệ thống. Tìm bội số chung nhỏ nhất Bội số chung nhỏ nhất (Least Common Multiplier – LCM) là số nguyên nhỏ nhất cùng chia hết cho a và b.