• Gọi $f(i,j)$ là số nghiệm của phương trình $a_1x_1+a_2x_2+...+a_ix_i=j$. Giả sử $x_i=k$, khi đó ta cộng $f(i,j)$ lên $f(i-1,j-a_ik)$
• ĐPT: $O(nm^2\times (\frac{1}{a_1}+\frac{1}{a_2}+...+\frac{1}{a_n}))$

• Với $n=2$, ta cần đếm số nghiệm không âm $(x,y)$ của phương trình Diophantine $ax+by=c$. Sử dụng thuật toán Euclid mở rộng, có được một nghiệm $(x_0,y_0)$ của phương trình. Gọi $d=gcd(a,b)$ thì tất cả các nghiệm của phương trình có dạng $(x_0 + k\times \frac{b}{d}, y_0 - k\times \frac{a}{d})$.
• Bây giờ chỉ cần đếm số số $k$ sao cho cả 2 nghiệm đều không âm. Ta có $x_0 + k\times \frac{b}{d}\geq 0$ nên $k\times \frac{b}{d}\geq -x_0$ nên $k\geq \frac{-x_0 d}{b}$. Tương tự, $k\leq \frac{y_0d}{a}$. Nhiệm vụ còn lại là đếm số số nguyên trong khoảng thỏa mãn của $k$.
• ĐPT: $O(\log m)$

• Dựng đồ thị $G=(V,E)$ có hướng như sau: Ta nối các đỉnh $(1,1)\rightarrow (2,1)\rightarrow (3,1)\rightarrow \cdots \rightarrow (n,1)$; với mỗi $i$ thì xây dựng chu trình $(i,1)\rightarrow (i,2)\rightarrow (i,3)\rightarrow \cdots \rightarrow (i,a_i)\rightarrow (i,1)$, cho ta một đồ thị có $S=a_1+a_2+...+a_n$ đỉnh.
• Giả sử từ đỉnh $(i,1)$ ta đi theo chu trình $i$ được $x_i$ lần, rồi đến đỉnh $(i+1,1)$ khi đó ta đã đi được thêm $a_ix_i+1$ cạnh. Vì vậy nên độ dài của đường đi từ $(1,1)$ đến $(n,1)$ là $a_1x_1+a_2x_2+...+a_{n}x_{n}+(n-1)$.
• Dễ thấy rằng việc tìm số bộ số $(x_1,x_2,...,x_n)$ thỏa mãn tương đương với việc tìm số đường đi từ $(1,1)$ đến $(n,1)$ có độ dài bằng $n+m-1$ ở đồ thị trên. Do đó sử dụng nhân ma trận để tính toán
• ĐPT: $O((a_1+a_2+...+a_n)^3 \times \log m)$

Code: https://ideone.com/XJAY8T

(Solution của anh thenymphsofdelphi)
Để đơn giản ta gọi phương trình $a_1x_1+a_2x_2+...+a_nx_n=v$ là $P(v)$. Định nghĩa $\overline {b_Mb_{M-1}...b_1b_0}$ là dãy bit của $m$ (cụ thể: $0\leq b_i\leq 1$, $m=b_M2^M+b_{M-1}2^{M-1}+...+b_12^1+b_02^0$).

Gọi $f(i,j)$ là số nghiệm của phương trình $P(\overline{b_Mb_{M-1}...b_i}-j)$, với $j\leq S=a_1+a_2+...+a_n$.

Nhận xét: tất cả các nghiệm của phương trình $P(\overline{b_Mb_{M-1}...b_{i+1}}-j)$ có thể tạo được tất cả các nghiệm của phương trình $P(\overline{b_Mb_{M-1}...b_{i+1}b_i}-j)$ nếu ta thay $x_i$ thành $2x_i$ hoặc $2x_i+1$.

• CM: Xét một nghiệm của phương trình $a_1x_1+a_2x_2+...+a_nx_n=\overline{b_Mb_{M-1}...b_{i+1}b_i}-j$. Đặt $x_i=2y_i+r_i$ thì $a_1x_1+a_2x_2+...+a_nx_n=a_1(2y_1+r_1)+a_2(2y_2+r_2)+...+a_n(2y_n+r_n)=2(a_1y_1+a_2y_2+...+a_ny_n)+a_1r_1+a_2r_2+...+a_nr_n$. Suy ra $2(a_1y_1+a_2y_2+...+a_ny_n)=\overline{b_Mb_{M-1}...b_{i+1}b_i}-j-(a_1r_1+a_2r_2+...+a_nr_n)$ hay $a_1y_1+a_2y_2+...+a_ny_n=\overline{b_Mb_{M-1}...b_{i+1}}-\frac{j+(a_1r_1+a_2r_2+...+a_nr_n)+b_i}{2}\geq \overline{b_Mb_{M-1}...b_{i+1}}-S$. Vì vậy 1 nghiệm $(x_1,x_2,..,x_n)$ của $P(\overline{b_Mb_{M-1}...b_{i+1}b_i}-j)$ luôn có thể tạo được từ 1 nghiệm $(y_1,y_2,...,y_n)$ của $P(\overline{b_Mb_{M-1}...b_{i+1}}-k)$, với $k\leq S$.

Qua nhận xét trên, ta có thể xét 1 nghiệm của phương trình $P(\overline{b_Mb_{M-1}...b_{i+1}}-j)$, duyệt toàn bộ $2^n$ cách chọn các bộ số $(r_1,r_2,...,r_n)$ và thay $x_i$ thành $2x_i+r_i$. Khi đó tổng mới sẽ là $\overline{b_Mb_{M-1}...b_{i+1}b_i}-2j+(a_1r_1+a_2r_2+...+a_nr_n)-b_i=$. Vì vậy ta cộng $f(i,2j+b_i-(a_1r_1+a_2r_2+...+a_nr_n))$ lên giá trị $f(i+1,j)$. Đáp số của bài toán là $f(0,0)$.

ĐPT: $O(\log m\times (a_1+a_2+...+a_n)\times 2^n)$.

Code: https://ideone.com/2PGorO