Một số kinh nghiệm giảng dạy về tính toán đồng dư cho học sinh giỏi quốc gia môn Tin Học

SỞ GIÁO DỤC VÀ ĐÀO TẠO THANH HOÁ
TRƯỜNG THPT CHUYÊN LAM SƠN
SÁNG KIẾN KINH NGHIỆM
MỘT SỐ KINH NGHIỆM GIẢNG DẠY VỀ TÍNH TOÁN ĐỒNG DƯ CHO HỌC SINH GIỎI QUỐC GIA 
MÔN TIN HỌC
Người thực hiện: Phạm Thị Nga
Chức vụ: Giáo viên
SKKN thuộc lĩnh vực (môn): Tin học
THANH HOÁ NĂM 2019
Mục lục
1. Mở đầu
1.1. Lí do chọn đề tài
Các bài toán trong thi học sinh giỏi quốc gia liên quan đến Toán học thường sẽ rơi vào hai mảng là số học và hình học. Nếu biết nhiều về số học, học sinh sẽ có khả năng giải quyết nhiều bài toán khó và một nền tảng tốt để giải quyết nhiều bài toán khác.
Các bài toán trong thi học sinh giỏi quốc gia thường đòi hỏi phải có một cái nhìn sâu sắc, vì vậy chỉ biết một số vấn đề về số học là không đủ. Mọi bài toán đều yêu cầu học sinh phải biết một lượng kiến thức toán nhất định. Ví dụ, một số bài toán yêu cầu học sinh phải giải một hệ nhiều phương trình hay tính xấp xỉ nghiệm của nhiều phương trình khác nhau. 
Tính toán đồng dư là một phạm trù khó, được tiếp cận và đưa vào thi cũng như trong giảng dạy, ôn luyện cho học sinh thi học sinh giỏi quốc gia những năm gần đây. Hiện tại, chưa có các tài liệu nghiên cứu nào bàn sâu vào vấn đề này, đồng nghiệp, nhà trường chưa có kinh nghiệm để giảng dạy nội dung nâng cao này. Vì vậy, trong hai năm học vừa qua, là giáo viên trực tiếp giảng dạy và phụ trách đội tuyển học sinh giỏi quốc gia tỉnh Thanh Hóa, tôi đã tìm hiểu và có “MỘT SỐ KINH NGHIỆM GIẢNG DẠY VỀ TÍNH TOÁN ĐỒNG DƯ CHO HỌC SINH GIỎI QUỐC GIA MÔN TIN HỌC”. Nay xin được trình bày đề tài này như là sáng kiến kinh nghiệm của bản thân tôi.
1.2. Mục đích nghiên cứu
	Nội dung thi học sinh giỏi tin học cũng như lập trình thi đấu ngày càng mở rộng và tăng độ khó do thực tiễn nhu cầu xã hội và bối cảnh phát triển của tin học, công nghệ thông tin hiện nay. Tính toán đồng dư là một nội dung mới, được mở rộng giới hạn bài toán và tốc độ xử lí, được tôi nghiên cứu và đưa vào giảng dạy cho học sinh đội tuyển học sinh giỏi quốc gia, nhằm cung cấp cho học sinh phần kiến thức mới, mở rộng, đồng thời rèn luyện cho học sinh các kĩ năng giải quyết những bài toán trong phạm vi thi học sinh giỏi quốc gia về tính toán đồng dư.
1.3. Đối tượng nghiên cứu
	Sáng kiến kinh nghiệm trình bày một số kinh nghiệm, phương pháp trong quá trình giảng dạy về tính toán đồng dư cho học sinh giỏi quốc gia và những kết quả mà tôi đã đạt được trong việc áp dụng nó giảng dạy cho đội tuyển học sinh giỏi tin học tỉnh Thanh Hóa năm học 2017 – 2018; 2018 – 2019.
1.4. Phương pháp nghiên cứu
Nghiên cứu lí thuyết ứng dụng
Phương pháp thực nghiệm khoa học
Phương pháp phân tích tổng kết kinh nghiệm
1.5. Những điểm mới của SKKN
Chưa có đồng nghiệp, tài liệu nào trình bày hoặc tổng hợp về kinh nghiệm giảng dạy phần tính toán đồng dư cho học sinh giỏi môn tin học.
Những kinh nghiệm này được trình bày thông qua việc nghiên cứu, giảng dạy cơ sở lí thuyết thuật toán và áp dụng giảng dạy từng bước cụ thể trên 4 bài toán điển hình áp dụng thuật toán theo cấp độ từ dễ đến khó, là những bài toán chưa được trình bày cách tiếp cận và lời giải ở một tài liệu nào khác.
2. Nội dung sáng kiến kinh nghiệm
2.1. Cơ sở lí luận của sáng kiến kinh nghiệm
2.1.1. Định nghĩa và các tính chất của hàm nhân tính
2.1.1.1. Định nghĩa
	- Hàm f(n) (n là số nguyên) là một hàm nhân tính nếu với mọi cặp số nguyên m, n nguyên tố cùng nhau thì f(m*n)=f(m)*f(n).
	- Hàm f(n) (n là số nguyên) là một hàm nhân tính hoàn toàn nếu với mọi cặp số nguyên m, n thì f(m*n)=f(m)*f(n).
2.1.1.2. Tính chất
	- Theo định lí số học cơ bản[1]: với mọi số nguyên dương n, tồn tại duy nhất một cách viết n dưới dạng tích của luỹ thừa các số nguyên tố:
	n=p1k1*p2k2*p3k3**paka sao cho k1, k2, k3, , ka là các số nguyên dương và p1, p2, p3, , pa là các số nguyên tố tăng dần.
	Nếu f(n) là một hàm nhân tính thì:
	f(n)=f(p1k1)* f(p2k2)*...*f(paka).
	fn=fp1k1*fn p1k1=fp2k2*fn p2k2==fpaka*fn paka.
	- Dirichlet Convolution[2]: Nếu f(n) và g(n) là hai hàm nhân tính thì:
	(f*g)(n)=d|nf(d)*g(n/d)
	cũng là một hàm nhân tính. 
2.1.1.3. Một số hàm nhân tính cơ bản
	- Hàm hằng 1(n) định nghĩa là 1(n)=1.	
	- Hàm định nghĩa id(n)=n.
	- Hàm luỹ thừa: fx=xc. (c là hằng số)
	- Cả ba hàm trên đều là hàm nhân tính hoàn toàn. 
2.1.2. Phương pháp để tính một hàm nhân tính
2.1.2.1 Chứng minh hàm cần tính là một hàm nhân tính
a. Chứng minh bằng công thức
	Nếu hàm f(n) có công thức không phụ thuộc vào việc nó có là hàm nhân tính không, để chứng minh f(n) là hàm nhân tính, ta có thể chứng minh f(n)*f(m)=f(m*n) (với mọi m, n nguyên tố cùng nhau) bằng cách biến đổi công thức. Ví dụ xét hàm f(n) là số ước của n.
	Nếu n phân tích ra thừa số nguyên tố có dạng n=p1k1*p2k2*p3k3**paka thì
	f(n)=(k1+1)*(k2+1)*...*(ka+1).
	Xét n và m nguyên tố cùng nhau và:
	n=p1k1*p2k2*p3k3**paka.
	m=q1h1*q2h2*q3h3**qbhb.
	thì m*n=p1k1*p2k2*p3k3**paka*q1h1*q2h2*q3h3**qbhb. 
	f(n)=(k1+1)*(k2+1)*...*(ka+1). 
	f(m)=(h1+1)*(h2+1)*...*(hb+1).
	f(m*n)= k1+1*k2+1*...*ka+1*(h1+1)*(h2+1)*...*(hb+1)=f(m)*f(n)
	nên f(n) là một hàm nhân tính.
b. Chứng minh sử dụng Dirichlet Convolution
	- Xét hai hàm f(n)=1 và g(n)=1, cả hai hàm này đều là hàm nhân tính nên theo Dirichlet Convolution, 
	f*gn=d|nfd*gnd=d|n1. Đây chính là hàm đếm số ước của n.
	- Đôi khi có những hàm chứng minh bằng cách biến đổi vất vả hơn rất nhiều so với sử dụng Dirichlet Convolution. Xét vì dụ hàm h(n) là tổng các ước của n. Sử dụng Dirichlet Convolution với hai hàm f(n)=n và g(n)=1 có:
	f*gn=d|nfd*gnd=d|nd=h(n).
	Nên h(n) là một hàm nhân tính.
2.1.2.2. Tìm cách tính trường hợp cơ bản
	- Hàm nhân tính giúp ta rút gọn việc tính f(n) cho mọi số nguyên dương n thành tính f(n) với n=pk, p là một số nguyên tố, k là số nguyên dương.
	- Nếu có công thức cho f(n) thì sử dụng công thức này.
	- Nếu không có công thức nhưng có một thuật toán để tính thì tính cho trường hợp này riêng.
2.1.2.3. Tính hàm nhân tính
	- Nếu chỉ tính một giá trị của hàm thì phân tích ra thừa số nguyên tố và tính riêng cho từng thừa số nguyên tố. Chỉ có tác dụng khi hàm này khó/ không có công thức để tính trong trường hợp chung.
	- Tính cho tất cả các giá trị x thoả mãn 1<=x<=n: Thực hiện sàng nguyên tố, trong lúc sàng với mỗi số lưu lại số nguyên tố bé nhất là ước của nó. Duyệt x tăng dần, kiểm tra kiểu của x. Nếu x là luỹ thừa của một số nguyên tố thì dùng thuật toán riêng để tính giá trị, nếu không thì dùng tính chất của hàm nhân tính để tính.
	Thuật toán trên có độ phức tạp là Onlogn+m*C với m là số luỹ thừa của số nguyên tố không vượt quá n và C là độ phức tạp để tính hàm cho luỹ thừa của một số nguyên tố. Thuật toán thực hiện sàng nguyên tố mất O(nlog(log⁡(n)), kiểm tra xem mỗi số có phải là số nguyên tố không mất Onlogn. Đặc biệt nếu hàm cần tính là hàm nhân tính hoàn toàn, độ phức tạp giảm còn là O(nlog(logn)+nlogn*C). Vì có O(nlogn) số nguyên tố <=n.[3] 
2.1.3. Tính toán đồng dư cơ bản
2.1.3.1. Định nghĩa
- Với mọi cặp số nguyên a và b (b>0), tồn tại duy nhất một cặp số nguyên q và r (0<=r<b) sao cho: a=b*q+r. Khi đó ta nói r là số dư khi chia a cho b và kí hiệu r=a mod b. Kí hiệu % để biểu diễn phép tính chia lấy dư (r=a%b).
- Hai số a và b thoả mãn a%m=b%m thì ta nói a và b đồng dư với nhau qua modulo m. Kí hiệu a≡b (mod m).
2.1.3.2. Các tính chất cơ bản và các phép tính
Các số a, b, c, d, k, m đều là số nguyên và m>0. 
-Tính đối xứng: a≡b (mod m) thì b≡a (mod m).
-Tính bắc cầu: a≡b (mod m) và a≡c (mod m) thì a≡c (mod m).
-Tính tương đồng khi cộng cùng giá trị: a≡b (mod m) thì a+k≡b+k (mod m). 
-Tính tương đồng khi nhân cùng giá trị: a≡b (mod m) thì a*k≡b*k (mod m). 
-Tính tương đồng khi cộng: a≡b (mod m) và c≡d (mod m) thì a+c≡b+d (mod m).	
-Tính tương đồng khi trừ: a≡b (mod m) và c≡d (mod m) thì a-c≡b-d (mod m). 
-Tính tương đồng khi nhân: a≡b (mod m) và c≡d (mod m) thì a*c≡b*d (mod m). 
-Tính tương đồng khi nâng lên cùng lũy thừa: a≡b (mod m) thì ak≡bk (mod m).
-Tính tương đồng khi tính toán đa thức: a≡b (mod m) thì P(a)≡P(b) (mod m) với mọi đa thức P(x) có các bậc và hệ số của các bậc nguyên.
-Tính loại trừ khi cộng: a+k≡b+k (mod m) thì a≡b (mod m)
-Tính loại trừ khi nhân: a*k≡b*k (mod m) thì a≡b (mod m) nếu k và m là hai số nguyên tố cùng nhau.
2.1.3.3. Nghịch đảo modulo
-Sự tồn tại: Với hai số nguyên a và m (m>0; 0<=a<m), tồn tại duy nhất một số nguyên b(0<=b<m) thoả mãn (a*b)%m=1 khi và chỉ khi a và m nguyên tố cùng nhau. Khi đó ta kí hiệu b=a-1 là nghịch đảo nhân modulo của a (mod m). Lưu ý rằng a-1 là một sự lạm dụng kí pháp vì a-1 không phải là một số nguyên khi a khác 1 hay -1, tuy nhiên vẫn được sử dụng thường xuyên để tiện cho việc trình bày.
-Tính tương đồng khi nghịch đảo modulo: Nếu a≡b (mod m) và tồn tại a-1 thì a-1 ≡b-1 (mod m).
-Nếu a*x≡b mod(m) và tồn tại a-1 thì x≡b*a-1 .
-Với số nguyên tố p thì tồn tại a-1 cho tất cả số nguyên a thoả mãn a%b khác 0.
2.1.4. Các định lí dùng tính toán đồng dư và hệ quả
2.1.4.1. Định lí nhỏ Fermat[4]
	Nếu p là một số nguyên tố thì với mọi số nguyên a, ap-a là một bội số của p.
-Kí hiệu: ap≡a (mod p).
-Hệ quả khi a và p nguyên tố cùng nhau: ap-1≡1 (mod p). Khi đó ap-2 là nghịch đảo modulo của a (mod p).
2.1.4.2. Hàm phi Euler
a. Định nghĩa và kí hiệu
	Hàm phi Euler cho một số nguyên dương n được định nghĩa là số lượng số nguyên dương a nguyên tố cùng nhau với n sao cho a<=n. Kí hiệu: ϕ(n). 
b. Công thức tính
	Công thức tích của Euler:
	ϕ(n)=n*p|n(1-1p) với mọi số nguyên tố p.
c. Tính chất của hàm phi Euler
	-ϕ(n) là một hàm nhân tính. 
	-ϕ(n) là số chẵn nếu n>2.
	-Nếu n=pk (n, k nguyên) với p là một số nguyên tố thì ϕn= pk-pk-1.
	-Lưu ý ϕ(1)=1.
d. Phương pháp tính hàm phi Euler
	-Tính một giá trị ϕ(n): Phân tích n ra thừa số nguyên tố và sử dụng công thức nhân Euler. Độ phức tạp của thuật toán này là độ phức tạp để phân tích n ra thừa số nguyên tố.
	-Tính tất cả các giá trị ϕ(x) với 1<=x<=n: Thực hiện sàng nguyên tố cho tất cả các số nguyên <=n.
	Duyệt các giá trị của x tăng, trong lúc sàng nguyên tố cũng lưu lại số nguyên tố nhỏ nhất là ước của x gọi số đó là p. Tìm pk với k lớn nhất sao cho pk|x.
	Nếu pk=x thì dùng công thức dành cho luỹ thừa của số nguyên tố, nếu không thì dùng tính chất của hàm nhân tính: ϕ(x)= ϕ(pk)* ϕ(x/pk).
const int maxp=1000000;
int p[maxp+1];
int phi[maxp+1];
void calculate_phi(){
 phi[1]=1;
 for(int i=2; i<=maxp; i++) 
 if(p[i]==0) 
 for(int j=i; j<=maxp; j+=i) 
 if(p[j]==0) p[j]=i;
 for(int i=2; i<=maxp; i++){
 int x=i; int t=p[i]; int k=1;
 while(x%t==0){
 k*=t; x/=t;
 }
 if(x>1) phi[i]=phi[k]*phi[x];
 else phi[i]=i-i/p[i];
 }
}
Code mẫu C++:
Code trên có độ phức tạp là O(nlog(n)) tuy nhiên thời gian chạy rất nhanh kể cả khi n=10^6.
e. Ứng dụng của hàm phi Euler trong tính toán đồng dư
	- Định lí Euler: Nếu hai số nguyên dương a và n nguyên tố cùng nhau thì:
	aϕ(n)≡1 (mod n).
	- Hệ quả của định lí Euler: aϕn-1≡a-1 (mod n) nếu a và n nguyên tố cùng nhau.
	- Hệ quả của định lí Euler: nếu hai số a và b thoả mãn a≡b (mod ϕ(n)) thì ka≡kb (mod n) nếu k và n nguyên tố cùng nhau.
2.1.4.3. Định lí phần dư Trung Hoa
a. Định nghĩa
	-Xét hệ phương trình đồng dư:
	x≡a1 (mod m1)x≡a2 (mod m2)x≡a3 (mod m3)x≡a4 (mod m4)x≡ak (mod mk)
	trong đó m1, m2, , mk đôi một nguyên tố cùng nhau.
	Định lí phần dư Trung Hoa chỉ ra rằng:
	Hệ phương trình đồng dư nói trên có nghiệm duy nhất theo modul
	 M=m1* m2**mk.
	nghiệm đó là x≡(i=1kai*Mi*yi) (mod n) với Mi=M/mi và yi=Mi-1 (mod mi) 
b. Trường hợp k=2
	-Vì m1, m2, , mk đôi một nguyên tố cùng nhau nên giải được trường hợp khi k=2 là sẽ giải được trường hợp tổng quát bằng cách thực hiện thuật toán k-1 lần, kiến cho việc cài đặt đơn giản hơn.
	-Ta có x≡a1 (mod m1) nên x=m1*q1+a1.
	 x≡a2 (mod m2) nên x=m2*q2+a2.
	Vậy m1*q1+a1=m2*q2+a2. Phương trình này có thể viết lại thành
	m1*q1+m2*q2=c với q1, q2, c là các số nguyên. Đây là một phương trình 	Diophantine tuyến tính, nên có thể giải được giá trị q1, q2 bằng giải thuật Euclid mở rộng[5], từ đó suy ra x.
2.2. Thực trạng vấn đề trước khi áp dụng sáng kiến kinh nghiệm
- Trong cả hai năm dạy bồi dưỡng đội tuyển học sinh giỏi quốc gia, hơn 60% học sinh đội tuyển chưa được tiếp cận với các bài toán về đồng dư, gần 40% học sinh còn lại dù đã được tiếp cận nội dung các bài toán đồng dư, nhưng chỉ bằng con đường tự tìm hiểu thêm các tài liệu chuyên môn trên internet và được viết bằng tiếng Anh là chủ yếu.
- Đồng nghiệp trong nhà trường và cả những trường chuyên bạn trong nước cũng có rất ít tài liệu, kinh nghiệm giảng dạy về tính toán đồng dư cho đối tượng học sinh giỏi, vì đây là một nội dung mở, mới.
2.3. Các giải pháp được sử dụng để giải quyết vấn đề
	Tôi đã đọc, tham khảo thêm các tài liệu viết về nội dung này trên internet, dịch thuật từ các tài liệu tiếng Anh trên các diễn đàn, website về thuật toán, lập trình thi đấu và tham khảo lời giải các kì thi tin học trong ba năm trở lại đây như IOI, APIO, BIO, ACM,... Từ đó nhận định và đưa ra các bài tập theo dạng, phân lớp bài toán theo mức độ từ dễ đến khó, dạy lí thuyết đến đâu áp dụng cho bài tập đến đó. Cho học sinh phân tích, đoán nhận giải thuật, sau đó hướng dẫn giải thuật, cho học sinh lập trình giải bài. Các bài tập đều được test cẩn thận cho học sinh, đánh giá độ phức tạp để học sinh có cơ sở so sánh, cảm nhận được sự tối ưu và cái hay, cái đẹp của lời giải, của thuật toán. Cụ thể, dưới đây là 4 bài tập được chọn lọc và lồng ghép đưa vào giảng dạy theo mức độ từ dễ đến khó.
Bài 1. POWERTOWER - Tháp luỹ thừa
Cho 2 số nguyên không âm n, a với a>0.
	Tháp luỹ thừa bậc n của a được định kí hiệu là a⇈n được định nghĩa:
a⇈n=1 khi n=0aa⇈(n-1) khi n>0=aaaa(n lần)
	Chú ý rằng khi tính giá trị tháp lũy thừa thì các phép lũy thừa được thực hiện theo thứ tự từ trên xuống.
Yêu cầu: Cho 3 số a, n, m tính (a⇈n)%m.
Input: Nhập vào dữ liệu từ file POWERTOWER.INP:
	Dòng đầu là số nguyên dương t, số bộ test.
	Trong t dòng tiếp theo, mỗi dòng 3 số nguyên dương a, n, m <=10^5 cách nhau bởi dấu cách.
Output: Với mỗi dòng dữ liệu từ file input, ghi ra file POWERTOWER.OUT một dòng là kết quả bài toán.
Ví dụ:
POWERTOWER.INP
POWERTOWER.OUT
6
1 4 100
4 2 100
3 3 1000
6 5 10000
2 100000 100
100000 20 78923
1
56
987
8656
36
41154
Thuật toán 
	- Định nghĩa hàm F(a, n, m) là kết quả của bài toán. Các trường hợp đặc biệt gồm có: 
	F(1, n, m)=1%m; 
	F(a, n, 1)=0; 
 	F(a, 0, m)=1%m; 
 	F(a, 1, m)=a%m;
	- Khi không trường hợp đặc biệt nào xảy ra, ta biết rõ a>1, m>1, n>1;
	- Nhận thấy rằng để rút gọn bài toán, cần sử dụng hệ quả thứ 3 của định lí Euler, tuy nhiên nhận thấy rằng gcd(a, m) chưa chắc chắn đã bằng 1, vì vậy cần chia m thành hai phần:
	m1 và m2 với m1*m2=m và gcd(a, m2)=1=gcd(m1, m2)=1 và sử dụng định lí phần dư Trung Hoa.
	- F(a, n, m2)≡aF(a, n-1, ϕ(m2)) (mod m2) tính được bằng cách gọi đệ quy tính F(a, n-1, ϕ(m2)) và dùng thuật toán luỹ thừa nhanh để tính trong O(log(F(a, n-1, ϕ(m2)))).
	- Để tính F(a, n, m1) thì nhận thấy là m110^5) nên a^x%m1=0 nếu x>=20. Xét các trường hợp sau:
	Nếu a=2 thì
	n>4=>F(a, n, m1)=0
	n<=4 có thể tính chính xác a⇈n
	Nếu a>=32 thì a⇈n>=20 vì n>1. 
	Nếu n>2 thì a⇈n>=20 vì 3⇈3>=20.
	Nếu không thì n=2 có thể tính được a^a bằng thuật toán luỹ thừa nhanh.
	- Sau khi tính được F(a, n, m1) và F(a, n, m2) sử dụng định lí đồng dư Trung Quốc và tính F(a, n, m). Có thể sử dụng cách tính nêu trên hoặc áp dụng thẳng công thức tổng quát.
Đánh giá độ phức tạp 
Với mỗi hàm F(a, n, m) được gọi, tính mất O(log(a)) vì:
	Tối đa 2 lần tính luỹ thừa nhanh. m1 và m2 tính trong log(a) vì có thể phân tích ra thừa số nguyên tố các giá trị này trong O(log(a)) nếu chuẩn bị sẵn mảng số nguyên tố bé nhất là ước trong khi sàng nguyên tố tính hàm phi Euler.
	Thoạt nhìn, độ phức tạp thuật toán sẽ là O(n*log(a)) cho mỗi test vì hàm F(a, n, m) có thể bị gọi tới n lần, tuy nhiên độ phức tạp thực tế là O(min(n, log(m))*log(a)) vì:
	Hàm F(a, n, m) gọi hàm F(a, n-1, ϕ(m2)) mà m23 nên từ lần đệ quy thứ 2, m2 chẵn hoặc m2<3. Nếu m2 là số chẵn thì ϕ(m2)<=m2/2 (dựa theo công thức nhân của Euler), nếu m2<3 thì m2=1. Do đó từ lần thứ 2 sau mỗi lần gọi hàm, m trong F(a, n, m) sẽ bị giảm đi ít nhất 2 lần, hay chỉ tốn tối đa log(m) lần gọi hàm cho đến khi gặp một trường hợp đặc biệt.
Code, Test và Cảm nhận
https://drive.google.com/file/d/16qWLNDlcVQMnz-ue2ob76__hKwXEHK1a/view
	Bài toán tháp luỹ thừa về mặt thuật toán thì thẳng thắn, đơn giản tuy nhiên lại yêu cầu có một số hiểu biết về tính toán đồng dư. Việc đánh giá đúng độ phức tạp cho ta một kết quả hay nhưng đơn giản mà lại khó tìm thấy. 
Bài 2. DPEQN - Congruence Equation
Cho phương trình đồng dư: a1x1 +a2x2 + ... + anxn = b (mod m)
Trong đó a1, a2, , an, b và m là các hằng số nguyên dương cho trước. x1, x2, , xn là các ẩn.
Tìm một nghiệm của phương trình trên, hoặc thông báo phương trình vô nghiệm.
Dữ liệu: Dòng đầu tiên ghi số bộ test, mỗi bộ test có dạng như sau:
Dòng 1: n (1 ≤ n ≤ 100)
Dòng 2: gồm n số nguyên a1, a2, , an (1 ≤ ai ≤ 108)
Dòng 3: b, m (1 ≤ b, m ≤ 108)
Mỗi bộ test được phân cách bởi một dòng trắng ở đầu.
Kết quả:
Với mỗi bộ test, nếu phương trình không có nghiệm, in ra dòng "NO". Trong trường hợp có nghiệm, in ra trên một dòng n số nguyên x1, x2, , xn (0 ≤ xi < m) là một nghiệm tìm được.
Ví dụ:
Dữ liệu
Kết quả
2
2
4 6
6 10
2
4 6
3 8
1 2
NO
Thuật toán
Vì đây là một phương trình đồng dư nên ta không cần quan trọng phải giải được nghiệm nguyên trong nửa khoảng [0, m], chỉ cần giải nghiệm nguyên bất kì là tìm được nghiệm trong khoảng đó.
Trước hết xét phương trình Diophantine 
	ax+by=c với a, b, c là hằng số có nghiệm khi gcd(a, b)|c. Thay đổi góc nhìn, ta có hàm hai chiều f(x, y)=ax+by=dk với d=gcd(a, b) có nghiệm với k là một số bất kì hay nói cách khác, nếu phương trình là ax+by, ta có thể rút gọn các giá trị có thể của nó về dk.
	Cứ đệ quy như vậy, phương trình trong đề bài trở thành dạng:
gcd(a1, a2, ...,an)*z = b (mod m)
	với z là một số nguyên nào đó. Phương trình trên có thể viết lại thành:
	gcd(a1, a2, ...,an)*z+t*m=b	với t cũng là một số nguyên.
	Đây lại là một phương trình Diophantine. Phương trình này có nghiệm thì có kết quả, nói cách khác bài toán có nghiệm khi và chỉ khi gcd(a1, a2, ...,an, m)|b. Việc kiểm tra xem phương trình có nghiệm hay không là đơn giản. Vậy làm thế nào để giải ra nghiệm khi có nghiệm?
	Đầu tiên giải gcd(a1, a2, ...,an)*z+t*m=b để tìm ra z. Đưa z về dạng 0<=z<m để tránh bị tràn số khi xử lí tiếp. Bây giờ phải giải
gcd(a1, a2, ...,an-1)*p+an*q=gcd(a1, a2, ...,an)*z.
	Phương trình này không khác gì phương trình mà ta bắt đầu với, nên giải tượng tự và thi được q, chính là ra trí của xn, sau đó lại đi giải tiếp
gcd(a1, a2, ...,an-2)*u+an-1*v=gcd(a1, a2, ...,an-1)*p
	Các bước đều như nhau nên có thể đệ quy để giải. Khi phương trình được rút gọn về dạng a1*x1+a2*x2=c thì có thể giải thẳng giá trị x1 và x2 luôn. Sau đó chỉ việc chuyển các giá trị về đúng dạng 0<=x<m (bằng cách mod cho m). 
	Mất O(n) lần tìm ước chung lớn nhất và O(n) lần giải phương trình Diophantine nên độ phức tạp là O(nlog(m)).
	Chú ý có thể cải thiện thời gian chạy bằng cách đệ quy tìm gcd của k số đầu tiên, thử xem k số đó đã đủ để giải phương trình chưa, nếu rồi thì cho tất cả các x còn lại bằng 0 là được. Cách này độ phức tạp xấu nhất vẫn sẽ là O(nlog(m)) tuy nhiên độ phức tạp trung bình xuống còn O(logm2+n) vì: Với số a, chuyển từ a đến gcd(a, b) thì gcd(a, b)=a hoặc gcd(a, b)|a=>gcd(a, b)<a/2. Xác suất để b là bội của a tương đối thấp nếu a lớn nêu sau trung bình O(log(a)) bước thì gcd(a, b) sẽ trở thành 1, đảm bảo giải được phương trình.
Test và cảm nhận 
Học sinh chấm bài tại đây https://vn.spoj.com/problems/DPEQN/
Bài DPEQN yêu cầu học sinh hiểu rõ bản chất của thuật toán Euclid mở rộng, phương trình Diophantine khi áp dụng trong tính toán đồng dư. Bài cũng yêu cầu khả năng cài đặt đệ quy, giúp giảm gánh nặng cho người cài đặt.
Bài 3. GCDSUM - Tổng các ước chung lớn nhất
Một lần, ktuan được thầy giáo cho bài tập v