{"id":"arxiv/2607.11477","url":"https://arxiv.org/abs/2607.11477","tags":["math.CO"],"score":0,"title":"Polynomial-Time Evaluation of Aardal-Lenstra Denumerants via Constant Term Method","domain":"math.CO","source":"arxiv","authors":["Jinlong Tang","Guoce Xin","Zihao Zhang"],"reviews":0,"subject":"math.CO","summary":"Aardal and Lenstra systematically studied hard knapsack problems of the form $a_1x_1+\\cdots+a_nx_n=b$, where $a_i=p_iM+r_iN$, $(M,N)$ is a coprime pair of positive integers, and the integers $|p_i|, |r_i|$ are small relative to $M$ and $N$. We investigate the corresponding challenging denumerant problem (i.e., counting the number of nonnegative integer solutions) and present a polynomial-time algorithm. This eliminates the computational bottlenecks caused by large values of $M$, $N$ and $b$. The proposed algorithm achieves a time complexity of $O(n^4Δ^2\\log n\\logΔ)$, which depends solely on…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-13","reactions":{}}