求x+a*y≤c非负整数解个数的O(1)紧凑公式（a,c为正实数）

问题回顾 #

我们需要计算非负整数对(x,y)满足不等式 x + a*y ≤ c（其中a、c为正实数）的解的个数。原方法是通过求和式计算：

sum( int(c - i*a) + 1 for i in range(int(c/a) + 1) )

现在探讨是否存在O(1)时间的紧凑公式。

核心推导 #

令 k_max = floor(c/a)（即y的最大可能取值），对于每个y=i（0≤i≤k_max），x的解数为 floor(c - i*a) + 1。将求和式展开并整理：
解的总数N可表示为：
$$
N = (k_{max} + 1) + \sum_{i=0}^{k_{max}} \lfloor c - i \cdot a \rfloor
$$
令 r = c \mod a（即0≤r<a，c = a·k_max + r），替换变量 t = k_max - i，求和式可转化为：
$$
\sum_{i=0}^{k_{max}} \lfloor c - i \cdot a \rfloor = \sum_{t=0}^{k_{max}} \lfloor t \cdot a + r \rfloor
$$
利用地板函数恒等式 \lfloor x \rfloor = x - \{x\}（其中\{x\}表示x的小数部分，0≤{x}<1），进一步展开：
$$
\sum_{t=0}^{k_{max}} \lfloor t \cdot a + r \rfloor = a \cdot \frac{k_{max}(k_{max}+1)}{2} + r(k_{max}+1) - \sum_{t=0}^{k_{max}} { t \cdot a + r }
$$
代入N的表达式并化简：
$$
N = (k_{max}+1)(c + 1) - \frac{a \cdot k_{max}(k_{max}+1)}{2} - \sum_{t=0}^{k_{max}} { t \cdot a + r }
$$

分情况结论 #

1. 当a为有理数时 #

设 a = p/q（p、q为互质正整数），此时 \{ t·a + r \} 的序列具有周期性，周期为q。我们可以预先计算一个周期内的小数部分和，再通过周期数与剩余项快速求和，最终得到精确的O(1)紧凑公式。

例如，若a=2/3，q=3，周期内的小数部分和可一次性计算，后续只需用 k_max // q 得到周期数，k_max % q 得到剩余项数，即可在常数时间内完成求和。

2. 当a为无理数时 #

根据Weyl均匀分布定理，\{ t·a + r \} 在[0,1)上均匀分布，其求和的近似值为 (k_max+1)/2，因此可得到近似公式：
$$
N \approx (k_{max}+1)(c + 0.5) - \frac{a \cdot k_{max}(k_{max}+1)}{2}
$$
但不存在仅由初等函数（地板函数、四则运算等）构成的精确紧凑O(1)公式，因为小数部分的求和无法用初等函数闭合表达，只能通过近似或特殊函数表示，不符合“紧凑”的初等公式要求。

内容的提问来源于stack exchange，提问作者ysa