Number of solutions of linear Diophantine equation.

Правка en1, от MS1908, 2019-07-26 05:09:33

So I'm having the following problem, which appeared in my university programming contest.

Problem: Given positive integers $$$M$$$ and $$$N$$$ $$$(1\le M\le 500,\,1\le N\le 100)$$$ and a $$$N$$$-tuple of positive integers $$$(a_1,a_2,...,a_N)$$$ $$$(1\le a_i\le 10,\, 1\le i\le N)$$$. Find the number of positive integers $$$N$$$-tuple $$$(k_1,k_2,...,k_N)$$$ such that $$$a_1k_1+a_2k_2+\cdots+a_Nk_N=M$$$.

Input: First line will be $$$N$$$ and $$$M$$$ $$$(1\le M\le 500,\,1\le N\le 100)$$$. Second line will be the tuple $$$(a_1,a_2,...,a_N)$$$ $$$(1\le a_i\le 10,\, 1\le i\le N)$$$.

Output: The number of solutions of the equation.

Теги #dynamic programming, #number theory

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский MS1908 2019-07-26 05:09:33 649 Initial revision (published)