请教关于线性不定方程非负整数解计数的问题

zgg___

给定a1、a2、……、an（它们都是大于1的实数），求不定方程x1/a1+x2/a2+……+xn/an<=1的非负整数解的组数。

求一种算法，在n<10^5、a<100的规模下能够解决问题。

wayne

把x1/a1+x2/a2+……+xn/an<=1 转化成整数系数的形式  b1*x1+b2*x2+...+bn*xn <=a1*a2*....an

倘若我们解方程b1*x1+b2*x2+...+bn*xn =a1*a2*....an  得到 x1=c1,x2=c2, ... , xn=cn .
那么原不等式解的个数就等于  (c1+1)(c2+1)....(cn+1) 了

wayne

哦，不对，方程b1*x1+b2*x2+...+bn*xn =a1*a2*....an   的解不唯一

那就这样，分别对 T属于 【0，a1*a2*....an】，解方程 b1*x1+b2*x2+...+bn*xn =T 的个数。然后相加

wayne

呃，规模太大了吧

wayne

a1、a2、……、an都是正整数就好说话了

求方程x1/a1+x2/a2+……+xn/an =1的非负整数解的组数T。
于是原不等式的解的个数就是  (1+a1)(1+a2)...(1+an) +T-2 的一半。

zgg___

a1、a2、……、an都是正整数就好说话了

求方程x1/a1+x2/a2+……+xn/an =1的非负整数解的组数T。
于是原不等式的解的个数就是  (1+a1)(1+a2)...(1+an) +T-2 的一半。
wayne 发表于 2011-12-16 18:06

正是这样的呢 ，如果它们都是正整数，题目可能就好算些了，因为所谓pick定理以及“Ehrhart polynomial”的东东就可以用上了呢。赫赫。

wayne

6# zgg___

俺仅仅根据n=2的情形，利用对称性拼凑出来的
好像不是很稳妥

我待会用软件验证一下

wayne

经验证，我那个计数的推广是错误的，好像仅仅对n=2成立。
pick定理以及 "Ehrhart polynomial"  才是正点。

罪过罪过。。。

shshsh_0510

pslq算法

zgg___

pslq算法
shshsh_0510 发表于 2011-12-19 10:18

对于PSLQ、LLL啥的稍稍有一点点了解。知道貌似这些东东可以用来求a1*x1+a2*x2+……+an*xn==1（其中an为已知实数，xn为要求解的未知正整数）的近似解（即==是约等于），但是不明白如何运用到本题中呢。请具体说说呢，赫赫。