Frobenius问题和denumerant的常数项方法

Frobenius 问题是关于一次不定方程的一个著名问题。设$a=(a_1,a_2,\dots, a_n)$是最大公约数为1的正整数，求不能表示成$m=a_1x_1+a_2x_2+\cdots + a_nx_n$ 的最大整数$m$，其中$x_1，x_2，…，x_n$为任意非负整数。这个问题称为一次不定方程的Frobenius问题，也称为换钱问题。该问题不仅在不定方程理论上有重要意义，还在规划论、计算技术、合理下料、合理派工等方面都有实际应用。对应的一个基础问题denumerant$d(m,a)$是$m=a_1x_1+a_2x_2+\cdots + a_nx_n$的表示方法数。本项目用常数项方法研究$d(m,a)$的快速算法，提出一个在$n$固定时猜想为多项式算法的新的快速实用算法，并用以推进Frobenius问题及其相关问题的研究。

The Frobenius problem is a famous problem concerning the linear indeterminate equation. Let $a = (a_1, a_2, \ dots, a_n) $ be positive integers with greatest common divisor 1. Find the largest integer $m$ that cannot be represented as $m = a_1x_1 + a_2x_2 + \ cdots + a_nx_n $, where $x_1, x_2,... , x_n$ can be any non-negative integers. This problem is called the Frobenius problem of the linear indeterminate equation, also known as the money exchange problem. This problem not only has important significance in the theory of indefinite equation, but also has practical application in the aspects of planning theory, computing technology, reasonable blanking and reasonable dispatching. The corresponding basic problem denumerant $d(m,a)$ is the number of ways to express $m=a_1x_1+a_2x_2+\cdots + a_nx_n$. This project uses the constant term method to study the fast algorithm of $d(m,a)$, proposes a new fast and practical algorithm which we conjecture to be polynomial when $n$ is fixed, and advances the study of Frobenius problem and its related problems.