Подсчитать количество решений для множественных переменных линейных диофантовых уравнений с взаимно простым коэффициентом

Question

Пусть общее диофантово уравнение имеет вид: a1*x1 + a2*x2 + .... + am*xm = n, где gcd(a1...am) = 1, (a1....am) >= 0

Я хочу найти количество неотрицательных (x1..xm) решений. Может ли кто-нибудь помочь мне с этим? Подробные математические объяснения или алгоритмы очень помогут.

Answer 1

То, что вы ищете, известно как "кузнец нормальной формы". Это объясняется, например, в википедии: http://en.wikipedia.org/wiki/Smith_normal_form В записи в википедии также объясняется стандартный алгоритм для такого рода проблем.

В вашем особом случае это в основном алгоритм евклидового gcd.